Segmentation and Paging

# Translate one address under each scheme, then count what each one wastes.
PAGE = 32
PAGE_TABLE = {0: 9, 1: 4, 2: 11, 3: 7}     # page number -> frame number
SEGMENTS = {1: (1400, 400)}                # segment -> (base, limit)

def translate_paged(logical):
    page, offset = divmod(logical, PAGE)   # a bit shift, since PAGE is 2**5
    frame = PAGE_TABLE[page]               # the offset is never translated
    return frame * PAGE + offset

def translate_segmented(seg, offset):
    base, limit = SEGMENTS[seg]
    if offset >= limit:                    # the bounds check IS the protection
        return None
    return base + offset

# Same three allocations under both schemes. Count what each one wastes.
requests = [60, 40, 30]                    # bytes each region needs

# Segmentation: variable-length regions. Freeing the middle one leaves a hole
# that only a request of exactly that size or smaller can ever use.
hole = requests[1]                         # 40-byte hole between two live segments
external_wasted = hole - 10                # a later 10-byte request fits; 30 stranded

# Paging: fixed frames, so any free frame fits any page. The only waste is the
# unused tail of the final page.
total = sum(requests)
pages = -(-total // PAGE)                  # ceiling division
internal_wasted = pages * PAGE - total

assert translate_paged(100) == 228         # page 3, offset 4 -> frame 7
assert translate_segmented(1, 53) == 1453
assert translate_segmented(1, 500) is None # past the limit: trap

print(f"segments: {external_wasted} wasted between holes "
      f"| pages: {internal_wasted} wasted inside the last page")

#include <iostream>
#include <vector>
#include <map>
#include <cassert>
using namespace std;
// Translate one address under each scheme, then count what each one wastes.
const int PAGE = 32;
map<int,int> PAGE_TABLE {
    {
        0,9
    },{1,4},{2,11},{3,7}
}; // page -> frame
map<int,pair<int,int>> SEGMENTS {
    {
        1,{1400,400}
    }
}; // segment -> {base,limit}
int translatePaged(int logical) {
    int page = logical / PAGE, offset = logical % PAGE; // a shift and a mask
    int frame = PAGE_TABLE[page]; // offset untranslated
    return frame * PAGE + offset;
}
int translateSegmented(int seg, int offset) {
    auto [base, limit] = SEGMENTS[seg];
    if (offset >= limit) return -1; // the bounds check IS the protection
    return base + offset;
}
int main() {
    vector<int> requests {
        60, 40, 30
    }; // bytes each region needs
    // Segmentation: freeing the middle region strands a hole that only a
    // request of that size or smaller can ever use.
    int hole = requests[1];
    int externalWasted = hole - 10; // a 10-byte request fits; 30 stranded
    // Paging: any free frame fits any page, so the only waste is the unused
    // tail of the final page.
    int total = 0;
    for (int r : requests) total += r;
    int pages = (total + PAGE - 1) / PAGE;
    int internalWasted = pages * PAGE - total;
    assert(translatePaged(100) == 228); // page 3, offset 4 -> frame 7
    assert(translateSegmented(1, 53) == 1453);
    assert(translateSegmented(1, 500) == -1);
    cout << "segments: " << externalWasted << " wasted between holes"
    << " | pages: " << internalWasted << " wasted inside the last page\n";
}

import java.util.*;
class Main {
    // Translate one address under each scheme, then count what each one wastes.
    static final int PAGE = 32;
    static final Map<Integer,Integer> PAGE_TABLE =
    Map.of(0, 9, 1, 4, 2, 11, 3, 7); // page -> frame
    static final Map<Integer,int[]> SEGMENTS =
    Map.of(1, new int[]{1400, 400}); // segment -> {base, limit}
    static int translatePaged(int logical) {
        int page = logical / PAGE, offset = logical % PAGE; // shift and mask
        int frame = PAGE_TABLE.get(page); // offset untouched
        return frame * PAGE + offset;
    }
    static int translateSegmented(int seg, int offset) {
        int[] s = SEGMENTS.get(seg);
        if (offset >= s[1]) return -1; // the bounds check IS the protection
        return s[0] + offset;
    }
    public static void main(String[] args) {
        int[] requests = {60, 40, 30}; // bytes each region needs
        // Segmentation: freeing the middle region strands a hole that only a
        // request of that size or smaller can ever use.
        int hole = requests[1];
        int externalWasted = hole - 10; // a 10-byte request fits; 30 stranded
        // Paging: any free frame fits any page, so the only waste is the
        // unused tail of the final page.
        int total = 0;
        for (int r : requests) total += r;
        int pages = (total + PAGE - 1) / PAGE;
        int internalWasted = pages * PAGE - total;
        assert translatePaged(100) == 228; // page 3, offset 4 -> frame 7
        assert translateSegmented(1, 53) == 1453;
        assert translateSegmented(1, 500) == -1;
        System.out.println("segments: " + externalWasted + " wasted between holes"
        + " | pages: " + internalWasted + " wasted inside the last page");
    }
}