{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Day 24 - Block Pool and Scheduler"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import math"
      ],
      "outputs": [],
      "execution_count": null
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "lengths=[32,128,64,256]; slots=max(lengths)*len(lengths); useful=sum(lengths); print(useful,slots,useful/slots)"
      ],
      "outputs": [],
      "execution_count": null
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "class BlockPool:\n",
        "    def __init__(self,n): self.free=list(range(n-1,-1,-1)); self.used=set(); self.peak=0\n",
        "    def alloc(self):\n",
        "        if not self.free: raise RuntimeError('out of blocks')\n",
        "        b=self.free.pop(); self.used.add(b); self.peak=max(self.peak,len(self.used)); return b\n",
        "    def free_block(self,b): self.used.remove(b); self.free.append(b)\n",
        "class PageTable:\n",
        "    def __init__(self,block_size): self.block_size=block_size; self.blocks=[]\n",
        "    def ensure_tokens(self,n,pool):\n",
        "        while len(self.blocks)<math.ceil(n/self.block_size): self.blocks.append(pool.alloc())\n",
        "    def physical_for_position(self,pos): return self.blocks[pos//self.block_size], pos%self.block_size\n",
        "pool=BlockPool(100); tables=[]\n",
        "for L in lengths:\n",
        "    pt=PageTable(16); pt.ensure_tokens(L,pool); tables.append(pt)\n",
        "print('used',len(pool.used),'static',len(lengths)*math.ceil(max(lengths)/16)); print([pt.blocks for pt in tables])"
      ],
      "outputs": [],
      "execution_count": null
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "pygments_lexer": "ipython3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}