External Fragmentation in OS

"""External fragmentation: free memory that is scattered, not contiguous."""


def coalesce(blocks):
    """Merge adjacent free runs. Blocks are [owner_or_None, size_kb]."""
    merged = []
    for owner, size in blocks:
        if owner is None and merged and merged[-1][0] is None:
            merged[-1][1] += size  # join the run we just added
        else:
            merged.append([owner, size])
    return merged


def free(blocks, name):
    """Release a named block, then merge any runs that became adjacent."""
    for block in blocks:
        if block[0] == name:
            block[0] = None
    return coalesce(blocks)


def holes(blocks):
    return [size for owner, size in blocks if owner is None]


def compact(blocks):
    """Slide live blocks down so all free space forms one run."""
    live = [b for b in blocks if b[0] is not None]
    free_total = sum(holes(blocks))
    return live + ([[None, free_total]] if free_total else [])


def main():
    memory = [["A", 12], ["B", 12], ["E", 5], ["C", 24], ["H", 20]]
    memory = free(memory, "B")
    memory = free(memory, "C")
    memory.append([None, 3])

    request = 26
    print(f"holes: {holes(memory)}  total free: {sum(holes(memory))} KB")
    print(f"largest run: {max(holes(memory))} KB")
    print(f"request {request} KB -> "
          f"{'fits' if max(holes(memory)) >= request else 'FAILS'}")

    memory = compact(memory)
    print(f"after compaction, largest run: {max(holes(memory))} KB")
    print(f"request {request} KB -> "
          f"{'fits' if max(holes(memory)) >= request else 'FAILS'}")


if __name__ == "__main__":
    main()

// External fragmentation: free memory that is scattered, not contiguous.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Block {
    std::string owner; // empty means free
    int sizeKb;
};
// Merge adjacent free runs into one.
std::vector<Block> coalesce(const std::vector<Block>& blocks) {
    std::vector<Block> merged;
    for (const Block& block : blocks) {
        if (block.owner.empty() && !merged.empty() && merged.back().owner.empty()) {
            merged.back().sizeKb += block.sizeKb;
        } else {
            merged.push_back(block);
        }
    }
    return merged;
}
int largestRun(const std::vector<Block>& blocks) {
    int largest = 0;
    for (const Block& block : blocks) {
        if (block.owner.empty()) {
            largest = std::max(largest, block.sizeKb);
        }
    }
    return largest;
}
int main() {
    std::vector<Block> memory {
        {
            "A", 12
        }, {"", 12}, {"E", 5}, {"", 24},
        {
            "H", 20
        }, {"", 3}
    };
    memory = coalesce(memory);
    const int request = 26;
    std::cout << "largest run: " << largestRun(memory) << " KB\n";
    std::cout << "request " << request << " KB -> "
    << (largestRun(memory) >= request ? "fits" : "FAILS") << '\n';
}

// External fragmentation: free memory that is scattered, not contiguous.
import java.util.ArrayList;
import java.util.List;
public class ExternalFragmentation {
    /** A region of memory. A null owner means the block is free. */
    record Block(String owner, int sizeKb) {
        boolean isFree() {
            return owner == null;
        }
    }
    /** Merge adjacent free runs into one. */
    static List<Block> coalesce(List<Block> blocks) {
        List<Block> merged = new ArrayList<>();
        for (Block block : blocks) {
            int last = merged.size() - 1;
            if (block.isFree() && last >= 0 && merged.get(last).isFree()) {
                merged.set(last,
                new Block(null, merged.get(last).sizeKb() + block.sizeKb()));
            } else {
                merged.add(block);
            }
        }
        return merged;
    }
    static int largestRun(List<Block> blocks) {
        return blocks.stream()
        .filter(Block::isFree)
        .mapToInt(Block::sizeKb)
        .max()
        .orElse(0);
    }
    public static void main(String[] args) {
        List<Block> memory = coalesce(List.of(
        new Block("A", 12), new Block(null, 12), new Block("E", 5),
        new Block(null, 24), new Block("H", 20), new Block(null, 3)));
        int request = 26;
        System.out.println("largest run: " + largestRun(memory) + " KB");
        System.out.println("request " + request + " KB -> "
        + (largestRun(memory) >= request ? "fits" : "FAILS"));
    }
}