DEV Community: Yash Jadhav

Implementing Multi-Level Feedback Queue in xv6

Yash Jadhav — Sat, 01 Aug 2026 18:30:28 +0000

So I have started learning internals of Operating System through OSTEP, and the plan is going to be implement each section from OSTEP into xv6 kernel.

What is xv6

xv6 is an educational open source operating system developed by MIT for teaching concepts of operating system.

Find more here: https://pdos.csail.mit.edu/6.828/2012/xv6.html
Github: https://github.com/mit-pdos/xv6-public
My implementation: https://github.com/lightsigma96/xv6-riscv

xv6 is minimal but contains all the important components needed to create an Operating System.

Understanding xv6 and QEMU

QEMU is a hypervisor and machine emulator which lets you have virtual hardware emulation required by the os.

As implementation of xv6 that I am using supports RISC-V assembly instructions and my CPU is x86_64, direct execution of instructions is not possible.

This is where QEMU steps in, it emulates the disk, RAM, CPU, etc and runs xv6, making xv6 think that it is actually executing RISC-V instructions on RISC-V hardware whereas in reality it is actually being executed on x86_64 system.

While modifying xv6 we can think that we are on actual RISC-V hardware and do not need to worry about translation.

Setting Up xv6

Setting up xv6 is straightforward, just have to use make with correct target to compile xv6 and connect via gdb to default port given.

Multi-Level Feedback Queue (MLFQ)

Now that xv6 is set up, what is MLFQ?

MLFQ is a scheduler policy which determine which process to schedule for CPU to execute depending on various factors.

Turnaround time:

This is the time which specifies the time difference between the time process arrived and the time when it completed executing.

So lets say three process A,B,C arrived where time take by A > B > C, in order to maximize this factor we can schedule C first as it takes least time and A at the last as it takes the most time.

Now the problem here is that unless C, B finish A can't do anything so this approach increases response time.

If the user is waiting for A's response of any kind they would have to wait for C, B to finish.

Response Time:

In order to make system more interactive, we can process all process partially so that user can at least see that the process is running and is responding.

We can have a time slice which is a interval after which we switch process and execute the next one.

So if A takes 10s, B takes 6s, C takes 2s, and our time slice/allocated time is 1s, then we will run all 3 processes in 3s which will make user feel that all process are interactive.

But one caveat over here is, if you look at time taken by each process, then C takes 2s while A takes 10s, with our time slice it would actually take 6s to finish process C whereas running it directly would have just taken 2s.

This is the trade off of optimizing for response time, we lose turnaround time.

SJF (Shortest Job First) optimizes for turnaround time while Round Robin uses allotment time and optimizes for response time.

MLFQ comes into picture

So how can we optimize for both turnaround time and response time? MLFQ can help us with it.

A MLFQ consists of multiple queues which are given different priorities as seen in the figure below.

The idea is that all jobs will be scheduled on the top most queue, and then will gradually be demoted to lower priority if they don't finish within the given time (aka allotment time).

This idea optimizes both allotment time and turnaround time, as jobs which are longer will be demoted down to lower queue so they don't block shorter jobs optimizing for turnaround time. We also give longer process some time (allotment time) which also optimizes for response time.

There is a catch, jobs which issues I/O basically are considered to be done within allotment time, but this causes problem as some bad program can issue I/O frequently causing it to stay on the same priority.

My experience while implementing MLFQ in xv6

When first writing code for xv6 you realize that you are modifying the kernel itself, which means there is no standard library, which means you don't have functions like malloc(), printf(), and most of the functions you use while writing user programs.

xv6 already provides implementation for malloc() as kalloc(), free() as kfree(), etc.

There is also this weird workflow that I had to get my head around, which was that I had to assume some of the events are automatically called and are not in my control like hardware traps (which entirely depends on implementation of risc-v cpu), also I studied how context switch actually happens and how data is copied into cpu registers and into memory.

There is also one thing not mentioned above, which is that, periodically all jobs are boosted to top queue, this is done to avoid starvation where if there are a lot of short jobs, longer jobs wouldn't get CPU at all.

I did this promoting by calculating the difference between CPU ticks when the jobs were last promoted to top priority queue.

Conclusion

This was a good lower level dive, almost at the lowest level I guess we can get just with software.

This was my attempt to implement a section of OSTEP (Operating System in Three Easy Pieces) which was cpu virtualization, up next is memory virtualization.

Will try to implement such more concept from OSTEP in this project.

Recall - An AI Mystery Game built with Cognee and Ollama

Yash Jadhav — Sat, 04 Jul 2026 12:37:07 +0000

Alright, so I had this idea of letting AI (not just LLM but maybe more than that) decide world generation, dialogue and actions of NPCs so that a game could feel more natural, it's like you are actually interacting with game.

So...this is my first and very small attempt towards it with Cognee and Ollama.

Recall is a terminal-based AI mystery game where you play as a detective investigating a murder. Your goal is to figure out the real killer by questioning suspects and piecing together their stories.

Check out the code here at Github which includes how to set it up and play:

lightsigma96 / Recall

A terminal mystery game where the truth isn't written — it's remembered. Talk to NPCs with real, persistent memory and piece together who did it, with no fixed script to follow.

Recall

An AI-driven murder mystery terminal game where every run creates a new story, suspects, killer, and conversations.

Players investigate by talking to NPCs. NPCs remember previous conversations, react dynamically, and provide clues based on the generated mystery.

Features

AI-generated murder mystery stories
Dynamic NPC personalities and conversations
Persistent NPC memory system
Procedurally selected killer and clues
Terminal-based interactive UI
Local (ollama) and cloud (Gemini) LLM support

How It Works

A new world and murder mystery are generated.
NPCs are created with unique personalities and knowledge.
Players interrogate NPCs.
Conversations are stored in memory.
Player uses gathered information to accuse the killer.

Game Stage	Cognee Cloud API	How Recall Uses It
NPC memory creation	`/api/v1/remember`	Stores each NPC's personality, secrets, relationships, and crime knowledge into a dedicated memory dataset
Memory isolation	Cognee datasets	Creates a separate dataset for every NPC (`npc_name_ds`) so suspects only know their own memories

…

View on GitHub

Building Memory of NPC

The main theme of this hackathon was memory.

An LLM only answer to the question prompted and does not retain any context.

For Recall every NPC has their own persistent memory powered by Cognee.

Whenever you interact with NPC, using cognee.recall() cognee searches through that NPC's existing memories and retrieves the most relevant information from their past interactions and initial backstory.

This information is used to answer player's question, once answered cognee.remember() is used to update that NPCs memory graph.

It's like Cognee is the brain and LLM is the mouth.

Every NPC has their own cognee dataset, which is created directly by calling cognee.remember() for initializing memory with some initial memory of incident, like where was the NPC when incident occurred, what were they doing and what do they know about the incident.

Additionally during initialization of NPCs each one is given a unique name, personality, and work.

The Whisper Feature

This is an experimental feature where NPCs can randomly interact with each other during the game and exchange memories.

The idea was to make the world feel more alive, where characters don't only react to the player but also influence each other.

This also means the criminal could eventually learn what questions you have been asking other NPCs and adapt accordingly.

I was able to build the core logic for this feature, but due to time constraints I couldn't properly integrate it into the game. The implementation can still be found in the codebase.

Game Setting

I wanted the themes to lean more towards mystery and detective settings, where the environment itself contributes to the investigation.

Initially I wanted to have 4 biomes/setting but again due to time constrain I was only able to add 2.

The story is generated by AI, so memory of every NPC and the story will be different on every playthrough, the only thing which is fixed is the setting of the game.

The 2 biomes are:

Victorian England which brings classic detective experience inspired by Sherlock Holmes, includes old buildings and characters.
Forest creates a more isolated and mysterious environment, surrounded by wilderness where every character has their own secrets hidden deep within the woods.

Cognee Cloud

We were provided with $35 of free cloud credits and it was really helpful.

Initially, Recall was running completely locally using Cognee along with an Ollama model. While this worked, running both memory operations and model inference locally became slow and resource-intensive, especially without access to high-end compute.

With cloud credits I could increase the speed of memory ingestion and recall.

Also it fixed a compatibility issue that I was having with a local ollama model by providing cloud-hosted infrastructure.

Making ASCII ARTS

Making ASCII Art seemed interesting at first but then quickly became a bottleneck as subtleties started surfacing.

I was using an image to ASCII converter so finding the right image is also an important task.

So for an ASCII art to look good it needs to have a lot of characters, and fitting them within a panel with other panel like Chat panel and header panel obviously meant decreasing the character count.

So I went ahead and did that, I reduced character count to 20, lowest I could go.

I was able to find correct images which were more expressive and different making them still comprehensible even with just 20 characters.

Well this did give a better look to the game.

Also this was the bottleneck due to which I could only make 2 levels and not 4.

Some ASCII Arts...they are comprehensible and there's the overflow I was talking about

Use of AI

Obviously, AI was also part of the development process.

Most of the code was handwritten, and the overall game design, architecture, and ideas were created by me. However, I used AI tools to speed up development when I wanted to quickly experiment, debug issues, or iterate on certain parts of the project.

For this project, I used ChatGPT and Claude through their websites, without any coding agents or external development harnesses, I don't have those :(

Ending

Recall is nowhere close to a complete game, but it represents an idea I wanted to experiment with, making NPCs feel less scripted and more alive.

Games can be much more fun when they feel more natural, interactive, and NPCs don't forget what they just said to you and how you interacted with them.

This was my first attempt at exploring that idea using Cognee and LLMs, and I am excited to see how far this approach can go.

How I Built a SQL Server From Scratch

Yash Jadhav — Sat, 16 May 2026 19:20:06 +0000

So I wanted to learn how to use SQL databases and what better way to than to build one and learn how things works, well couldn't cover as much as planned still touched core components and basic queries. Here is how I started.

Resources that I referred to

Architecture of a Database System (majorly)
database-management-systems-raghu-ramakrishnan (for query planner & optimization)

Source

https://github.com/lightsigma96/db_scratch

lightsigma96 / db_scratch

This is a simple single-threaded database built for learning purposes.

It supports basic operations such as:

Creating schemas
Creating tables
Inserting rows

Supported data types:

INT
STRING
FLOAT

Build and Run (Local)

Build the project using CMake:

cmake -S . -B build
cmake --build build

Run the database:

./build/db_scratch

Using Docker

A Dockerfile is provided to build and run the project inside a container.

Build the image

docker build -t db_scratch .

Run the container (interactive)

docker run -it db_scratch

Inside the container:

./build/db_scratch

Notes

The Docker image includes build tools and is intended for both development and debugging.
If you modify the source code, rebuild the image:

docker build -t db_scratch .

CMake

Uses a basic CMake setup for building the project.

View on GitHub

Storage Manager

This is the core of disk-based database, it's function is to interact with disk,
handle various db files and manage pages.

Buffer Pool

Buffer Pool caches pages from heap files in memory (which are responsible for storage of rows), pages are small fragments of heap file which are of fixed size (4kb in my case).

Reading or Writing from heap file on disk can be slow, hence pages from heap
file are loaded into memory (RAM) through buffer pool which is much faster.

Now obviously we cannot load entire file into memory, as that that can lead to out of memory error.

Hence we load file in pages into buffer pool which sits in memory.

Buffer Pool has a page replacement policy which evicts certain pages when buffer
pool is full.

In my case I implemented a simple FIFO replacement policy which tracks pages in
order of insertion into buffer pool, which checks if the page is pinned (pages which are frequently used or are being used by some component are pinned, pin count shows how many components are using that page), if yes then send them back in the queue, if no then flush them (write to disk) and evict them.

Buffer pools also contains a Disk Operator responsible for writing to file and
other things (implementations can vary).

Access Methods

Access Methods provides with necessary data structure and algorithms to organize
and access data.

On heap file rows are stored one after another and heap scan from access methods scan each one of them to find correct row based on given SARG.

SARGs (Search Arguments) describes condition for finding a row, they contain
column, operator and constant.

Heap scan may require scanning all rows across multiple pages resulting in O(n)
search complexity, hence a index scan can be implemented using B+ Trees.

B+ Tree consists of leaf nodes and internal nodes, Leaf nodes store key and RID (Row Identifier) which points to the exact row in heap file,

B+ Tree reduces index traversal cost from scanning many pages to traversing a small number of pages proportional to tree height, after which corresponding heap pages can be accessed using RID.

The downside of index scan is that index keys are built on specific columns.If query predicates do not use indexed columns then planner may fallback to heap scan.

Query Planner and Optimizer

After Buffer Pool and Access Methods, rows can be stored on disk and retrieved,
next comes the query planner & optimizer which makes plan for execution of query
and optimizes that plan.

Lexer & Parser

Queries are tokenized into keywords, identifiers, literals and special symbols
which are then passed to parser.

Parser is responsible for checking grammar and construct AST based on tokens
passed.

Parser's implementation can vary, in my case Lexer provides a tokenizer which is
used to iterate token forward/backward, and peek tokens.

Parser uses these token to check grammar of different queries.

Once this has been done Parser produces an AST specific to each query.

Planner and Optimizer

The AST produced by Parser is consumed by Planner which has a plan defined for
each query.

For example plan for select query involves three steps (from top to bottom):

Projection : Selects specific columns from tuples returned by child operators.

Filter : Based on SARG matching, this steps filters out rows returned by heap scan.

Scan : This calls heap scan and returns the output above in the chain.

(Rows flow upward from Scan → Filter → Projection)

Each operator pulls one tuple at a time from its child operator.

Optimization depends on type of query, for example if a index for columns exists then index scan can be used instead of heap scan.

Catalog Manager

Catalog Manager is logically separate from query execution components and is
responsible for schema metadata management.

This is used to enforce schema and handle writing and reading to/from a schema file.

To write schema to a file a serializer has to be made which writes schema in
format:

Schema name size
Schema name
- heap page offset
- heap page id
- Table name size
- Table name
- - Column size
- - Column name

The only caveat here is, before every name I had to store it's size as I have used C++ string over here which stores pointer to actual string allocated in memory, so if I directly write it on file, I would be writing garbage memory address.

Deserializer reads this back from file.

Main Server

This initializes all the necessary objects like buffer manager, access methods,
query planner, catalog manager.

I have two pipelines, DB Pipeline, TUI Pipeline, initially I wanted to have a
client-server architecture with a tcp server requesting DB but instead I thought
of going with direct function calls.

DB Pipeline

This function is responsible for orchestration of database pipeline (A TCP server can also be created which would be responsible for preprocessing cli input and calling db).

First the input query is tokenized and checked for correctness by lexer and parser.

If query is valid then AST is generated which is then goes through their respective processing (like for SELECT query it is passed through select plan and create table is passed through create table provided by catalog manager).

A response is finally returned by this function, implementation for this pipeline can be different.

With all the things above a database can support basic things like creating schema,table,columns executing basic queries like SELECT, INSERT, DELETE (same architecture can be extended to support JOINS and Stored Procedure).

Some other core components included:

WAL (Write Ahead Log): Ensures durability and crash recovery by logging changes before modified pages are written to disk. Follows ACID properties.
Lock Manager: Used to gain locks for multi-threading.