/solve-maths-mem · foundations
Memory tiers and the FIFO queue
MemGPT treats the context window as an operating system treats RAM: a small tier the processor reads directly, a large tier reached by explicit transfers, and a rule for what to evict [Packer et al., §2].
Five tiers, three vocabularies
| MemGPT | operating system | /solve-maths-mem |
|---|---|---|
| \(\mathrm{sys}\) | kernel code in read-only pages: rules every process obeys, changed only by a new release | SKILL.md + the Fix |
| \(W\) | the saved state of a process at a context switch: small, fixed layout, enough to resume | memory/core.md |
| \(Q\) | pages in RAM, the oldest evicted first when RAM is full | the root's messages |
| Recall | a journal (log): every event appended, never edited | briefs/, returns/, events.jsonl |
| Archive | the file system: named, durable records, opened on demand | tree.json, solve/library.jsonl |
One example of each, from the satake-two-levels run: Design · one of each. Textbook: [OSTEP, chapters on paging and swapping].
The FIFO queue
(queue) [CLRS, §10.1]
A queue is a sequence \((q_1,\dots,q_\ell)\) with two operations, first in, first out:
$$\mathrm{enqueue}(x):\ (q_1,\dots,q_\ell)\mapsto(q_1,\dots,q_\ell,x),\qquad \mathrm{dequeue}:\ (q_1,\dots,q_\ell)\mapsto q_1,\ \ (q_2,\dots,q_\ell).$$In memory: a row of slots
Memory is a row of numbered boxes. A buffer reserves \(c\) of them, slots \(0,\dots,c-1\): \(c\) is the capacity, fixed when the buffer is made. Write slot \(s\) = put a value in box \(s\), overwriting what was there; read slot \(s\) = copy out what box \(s\) holds.
| layout | dequeue | cost |
|---|---|---|
| \(q_1\) always in slot 0 | read slot 0, shift every item one slot left | \(\ell-1\) copies |
| ring buffer | read slot \(h\), then \(h\leftarrow(h+1)\bmod c\); items stay put | 1 read |
The ring's whole state is two numbers, the front \(h\) and the length \(\ell\); the next free slot \(t\) is computed, not stored. “\(\bmod c\)” is what bends the row into a ring: after slot \(c-1\) comes slot 0.
$$t=(h+\ell)\bmod c;\qquad \mathrm{enqueue}(x):\ \text{slot}[t]\leftarrow x,\ \ell\leftarrow\ell+1;\qquad \mathrm{dequeue}:\ x\leftarrow\text{slot}[h],\ h\leftarrow(h+1)\bmod c,\ \ell\leftarrow\ell-1.$$queue, front → back: · next free slot \(t\) =
- in the queue
- old value, free to overwrite
- h next out
- t next in
(trace a ring buffer) compute
Start empty with \(c=4\), \(h=0\). Run: enqueue a, enqueue b, enqueue c, dequeue, enqueue d, enqueue e, dequeue, enqueue f. Give the two dequeued items, the final array, \(h\) and \(\ell\). Then check with “step through the trace exercise” in .
Dequeued a, then b. Final array \([\mathrm{e},\mathrm{f},\mathrm{c},\mathrm{d}]\), \(h=2\), \(\ell=4\) (full); front to back: c, d, e, f.
enq a → slot 0 enq b → slot 1 enq c → slot 2 deq → a, h=1 enq d → slot (1+2) mod 4 = 3 enq e → slot (1+3) mod 4 = 0 deq → b, h=2 enq f → slot (2+3) mod 4 = 1
(why keep \(\ell\)?) predict
Store the next free slot \(t\) instead of \(\ell\). In the widget, make the queue empty, then full (\(\ell=c\)). What are \(h\) and \(t\) in each case?
\(h=t\) in both: \((h,t)\) cannot tell empty from full. Two fixes: keep \(\ell\) (this page), or never fill the last slot, so “full” means \((t+1)\bmod c=h\) and the queue holds at most \(c-1\) items (CLRS’s choice; you code it in Coding a queue).
(what FIFO keeps) misconception
When \(Q\) is full, MemGPT evicts from the head. Which messages stay?
The most recent. FIFO knows only arrival order, so an old message the root still needs (R-1's registry at 02:56, say) is evicted before a newer one it does not need. That is why the registry belongs in \(W\), which is never evicted, and not in \(Q\).
History
| year | advance |
|---|---|
| 1909 | calls waiting at a telephone exchange: queueing theory begins [Erlang] |
| 1962 | Atlas: a small fast store holds pages of a large slow one, moved automatically (paging) [Kilburn et al.] |
| 1965 | bounded buffer of \(N\) portions between a producer and a consumer, guarded by semaphores; “a first-in-first-out memory” [Dijkstra, §4.1, §4.3] |
| 1966–69 | replacement policies compared with the optimum MIN; FIFO can fault more with more frames [Belady; Belady et al.] |
| 1968 | a queue in \(M\) array slots used in a circle, with OVERFLOW and UNDERFLOW checks: the ring buffer above [Knuth, §2.2.2] |
| 1972–73 | Unix pipes: a kernel FIFO of up to 4096 bytes between two processes (stored in a file, not a ring) [Ritchie; McIlroy] |
| 2009 | textbook form: one slot left free, Exercise 10.1-4 (coded here) [CLRS, 3rd ed., §10.1] |
| 2023 | MemGPT: a FIFO of messages in the context window, evicted to recall storage [Packer et al., §2.1–2.2] |
Which page to evict
(paging) [OSTEP; Belady 1966]
A program touches pages \(p_1,p_2,\dots,p_T\) (the reference string); RAM holds \(c\) of them (frames). Touching a page not in RAM is a fault: it is loaded, and if RAM is full one page is evicted by a policy:
$$\textbf{FIFO}:\ \text{loaded earliest};\qquad \textbf{LRU}:\ \text{used least recently};\qquad \textbf{OPT}:\ \text{next used farthest in the future}.$$- fault: the page was not in RAM and is loaded
- hit: already in RAM
- ◯ FIFO faults more with one more frame
(more memory, more faults) predict
On \(1,2,3,4,1,2,5,1,2,3,4,5\), predict FIFO's faults with \(c=3\) and with \(c=4\). Then check with the buttons above.
9 with \(c=3\), 10 with \(c=4\): Belady's anomaly [Belady, Nelson, Shedler]. LRU and OPT never do this: the pages they hold with \(c\) frames are always among those they hold with \(c+1\) (the inclusion property of stack algorithms [Mattson et al.]). FIFO's contents with \(c\) frames need not be among those with \(c+1\).
(the root knows the future) transfer
OPT needs the future reference string, so an operating system cannot run it. After R-1 the root wrote its next action: “A7 audits A2, A4, A6; A8 attacks the \(E_6/F_4\) sheaf level.” Which steps will it need next, and what does that say about evicting by FIFO?
The returns of A2, A4, A6 and the \(E_6/F_4\) row: the next action names them. The root is closer to OPT than an operating system is, because it writes down its own future references. So it should keep them by choice in \(W\) (ids and one line each) and let FIFO evict only what no next action names.
MemGPT's queue manager
MemGPT's \(Q\) is a FIFO of messages whose head is a running summary; \(\mathrm{sys}\) and \(W\) are never evicted; the thresholds are the paper's example values [Packer et al., §2.2]:
$$|\mathrm{main}|=|\mathrm{sys}|+|W|+|Q|;\qquad |\mathrm{main}|\ge 0.7\,c_{\max}\Rightarrow\text{warning};\qquad |\mathrm{main}|\ge c_{\max}\Rightarrow\text{evict}\approx0.5\,c_{\max}\ \text{to Recall, re-summarize}.$$(when does it flush?) compute
\(c_{\max}=8000\), \(|\mathrm{sys}|=1200\), \(|W|=800\), every message 400 tokens, \(Q\) empty at the start, and a summary of 300 tokens after a flush. After which message comes the warning, after which the first flush, how many messages does it evict, and how many more messages until the second flush?
Tokens in context after each message: the warning line is crossed at \(j=9\), the flush line at \(j=15\) and \(j=25\).
Warning after message 9, flush after message 15 (10 messages to Recall), second flush 10 messages later. Recall holds every message, so after the flush it holds all 15.
(what the summary replaces) misconception
After a flush, where is the exact text of an evicted message?
In Recall. The summary is a lossy pointer in the context; the text is kept verbatim outside it [Packer et al., §2.2]. In a solve run the evicted return is still returns/A2.json.
Next: exercises on \(\mathrm{sys}\) and \(W\), then on Recall and Archive.