Building a Minimal OS from Scratch

The CPU starts in Real Mode: 16-bit registers, segmented addressing (physical = segment × 16 + offset), maximum 1 MB RAM. Your bootloader must transition to Protected Mode — a 32-bit flat address space — before calling C code. The steps are strictly ordered:

The GDT defines memory segments. Each entry (descriptor) is 8 bytes and encodes a base address, a limit, and access/flag bytes. For a flat kernel we use base = 0, limit = 4 GB for both code and data so the entire 32-bit address space is accessible as a single segment.

; GDT layout in boot.asm — 3 entries × 8 bytes = 24 bytes
gdt_null:   dd 0, 0              ; Entry 0: null (required)

gdt_code:                           ; Entry 1: selector 0x08
    dw 0xFFFF                       ; Limit bits 15:0
    dw 0x0000                       ; Base  bits 15:0
    db 0x00                         ; Base  bits 23:16
    db 0x9A                         ; Access: P=1 DPL=0 S=1 Code R/X
    db 0xCF                         ; Flags: G=1(4KB) DB=1(32-bit) + Limit 19:16
    db 0x00                         ; Base  bits 31:24

gdt_data:                           ; Entry 2: selector 0x10
    dw 0xFFFF
    dw 0x0000
    db 0x00
    db 0x92                         ; Access: P=1 DPL=0 S=1 Data R/W
    db 0xCF
    db 0x00

In Protected Mode there are no BIOS calls. To print text we write directly to the VGA text buffer at 0xB8000. The buffer is a 80×25 grid of 16-bit cells. The low byte is the ASCII character; the high byte is the attribute (background colour in bits 7–4, foreground in bits 3–0).

#define VGA_BUFFER  ((volatile uint16_t *)0xB8000)
#define VGA_COLS    80
#define VGA_ROWS    25

/* Build a VGA cell: attribute byte | ASCII char */
static inline uint16_t vga_cell(char c, uint8_t attr) {
    return (uint16_t)((attr << 8) | (uint8_t)c);
}

/* Write character at (row, col) */
static void vga_putchar_at(char c, uint8_t attr, int row, int col) {
    VGA_BUFFER[row * VGA_COLS + col] = vga_cell(c, attr);
}

/* Hardware cursor: CRT controller ports 0x3D4 / 0x3D5 */
void vga_update_hw_cursor(int row, int col) {
    uint16_t pos = (uint16_t)(row * VGA_COLS + col);
    outb(0x3D4, 0x0F); outb(0x3D5, (uint8_t)(pos & 0xFF));
    outb(0x3D4, 0x0E); outb(0x3D5, (uint8_t)(pos >> 8));
}

The shell is a simple read-eval loop. keyboard_readline() blocks on PS/2 port 0x60 polling until Enter is pressed, echoing each character to the VGA display. The completed line is tokenised on whitespace and the first token is looked up in a command table.

/* Command table entry */
typedef struct {
    const char  *name;
    const char  *help;
    void       (*fn)(int argc, char *argv[]);
} command_t;

/* Shell main loop — never returns */
void shell_run(void) {
    char  line[256];
    char *argv[16];
    for (;;) {
        print_prompt();
        keyboard_readline(line, sizeof(line));
        int argc = tokenise(line, argv, 16);
        if (argc == 0) continue;
        dispatch(argc, argv);   /* look up commands[] table */
    }
}

The starter kit provides: help, clear, echo, version, colour, halt. Stages 1–4 add: ps, kill, meminfo, ls, touch, cat, write, rm.

$ make
  AS    boot/boot.asm
  CC    kernel/kernel.c
  CC    kernel/shell.c
  CC    kernel/string.c
  CC    drivers/vga/vga.c
  CC    drivers/keyboard/keyboard.c
  LD    build/kernel.elf
  BIN   build/kernel.bin
  IMG   seng21213.img  (34K)

$ make run
# Expected QEMU output:
# [  OK  ] VGA driver initialised
# [  OK  ] PS/2 keyboard driver initialised
# +=================================================+
# |   SENG 21213 - Stage 0 Kernel Shell            |
# |   Type 'help' for available commands            |
# +=================================================+
# kernel> _

Every process is described by a PCB stored in a fixed-size array — the process table. The fields that matter most for Stage 1 are the saved stack pointer (used to restore registers on context switch) and the process state.

/* include/process.h */
#define MAX_PROCS   16
#define STACK_SIZE  4096     /* 4 KB kernel stack per process */

typedef enum {
    PROC_UNUSED = 0,
    PROC_READY,
    PROC_RUNNING,
    PROC_BLOCKED,
    PROC_ZOMBIE,
} proc_state_t;

typedef struct {
    uint32_t      pid;
    proc_state_t  state;
    uint32_t      esp;          /* saved stack pointer (set on context switch) */
    uint32_t      stack_base;   /* bottom of this process's stack              */
    void        (*entry)(void); /* entry point function                        */
    char          name[32];
    uint32_t      ticks;        /* total CPU ticks consumed                    */
} pcb_t;

extern pcb_t proc_table[MAX_PROCS];
extern int   current_proc;

pcb_t *proc_create(const char *name, void (*entry)(void));
void   proc_exit(void);

The IDT (Interrupt Descriptor Table) tells the CPU which handler to call for each interrupt vector. Vector 0–31 are CPU exceptions; vectors 32–47 are IRQs from the PIC. We remap the PIC so IRQ0 (timer) → vector 32, then program the i8253 PIT for 100 Hz.

/* kernel/idt.c */
#define PIC1_CMD   0x20
#define PIC1_DATA  0x21
#define PIC2_CMD   0xA0
#define PIC2_DATA  0xA1
#define PIT_CH0    0x40
#define PIT_CMD    0x43
#define PIT_HZ     100          /* 10 ms tick */
#define PIT_DIVISOR (1193182 / PIT_HZ)

void pit_init(void) {
    /* Remap PIC: IRQ0-7 → vectors 32-39, IRQ8-15 → 40-47 */
    outb(PIC1_CMD,  0x11); outb(PIC2_CMD,  0x11);
    outb(PIC1_DATA, 0x20); outb(PIC2_DATA, 0x28);
    outb(PIC1_DATA, 0x04); outb(PIC2_DATA, 0x02);
    outb(PIC1_DATA, 0x01); outb(PIC2_DATA, 0x01);
    outb(PIC1_DATA, 0x00); outb(PIC2_DATA, 0xFF);

    /* Program PIT channel 0: rate generator, divisor for 100 Hz */
    outb(PIT_CMD, 0x36);
    outb(PIT_CH0, (uint8_t)(PIT_DIVISOR & 0xFF));
    outb(PIT_CH0, (uint8_t)(PIT_DIVISOR >> 8));
}

The context switch must save all registers of the outgoing process and restore those of the incoming process. PUSHAD saves EAX, ECX, EDX, EBX, ESP (before PUSHAD), EBP, ESI, EDI — 32 bytes — onto the current stack. We store ESP in the PCB, swap to the new process's ESP, then POPAD restores that process's registers.

; boot/switch.asm
; context_switch(uint32_t *old_esp, uint32_t new_esp)
;   [esp+4] = pointer to save old esp into
;   [esp+8] = new esp value to load
global context_switch
context_switch:
    pushad                      ; Save EAX ECX EDX EBX ESP EBP ESI EDI
    mov  eax, [esp + 36]        ; arg0: old_esp ptr  (36 = 8 regs × 4 + ret)
    mov  [eax], esp             ; *old_esp = current ESP
    mov  esp, [esp + 40]        ; arg1: new_esp — switch stacks
    popad                       ; Restore next process's registers
    ret                         ; Return into next process's code

/* kernel/scheduler.c */
void scheduler_tick(void) {
    proc_table[current_proc].ticks++;

    /* Find the next READY process (wrap around) */
    int next = (current_proc + 1) % MAX_PROCS;
    int searched = 0;
    while (searched < MAX_PROCS) {
        if (proc_table[next].state == PROC_READY) break;
        next = (next + 1) % MAX_PROCS;
        searched++;
    }
    if (searched == MAX_PROCS) return; /* no other process — keep running */

    int old = current_proc;
    proc_table[old].state  = PROC_READY;
    proc_table[next].state = PROC_RUNNING;
    current_proc = next;

    /* Send EOI to PIC before switching so the next tick fires */
    outb(0x20, 0x20);

    context_switch(&proc_table[old].esp, proc_table[next].esp);
}

/* Add to commands[] table in kernel/shell.c */
static void cmd_ps(int argc, char *argv[]) {
    (void)argc; (void)argv;
    vga_printf("%-4s %-12s %-10s %s\n",
               "PID", "NAME", "STATE", "TICKS");
    vga_puts("---- ------------ ---------- -----\n");
    for (int i = 0; i < MAX_PROCS; i++) {
        if (proc_table[i].state == PROC_UNUSED) continue;
        const char *states[] = {"UNUSED","READY","RUNNING","BLOCKED","ZOMBIE"};
        vga_printf("%-4d %-12s %-10s %u\n",
            proc_table[i].pid, proc_table[i].name,
            states[proc_table[i].state], proc_table[i].ticks);
    }
}

A kernel thread is almost identical to a process in Stage 1 — it has its own stack and saved ESP. The key difference is that threads belonging to the same process share all other resources (code, data, heap). For our flat-memory kernel this means we just allocate a new stack region and let the scheduler treat it the same as any other runnable unit.

/* include/thread.h */
typedef struct {
    uint32_t  tid;
    uint32_t  pid;            /* parent process */
    uint32_t  esp;            /* saved stack pointer */
    uint8_t   stack[STACK_SIZE];
    proc_state_t state;
    char      name[24];
} tcb_t;

tcb_t *thread_create(uint32_t pid, const char *name,
                      void (*fn)(void));
void   thread_exit(void);

The classic demonstration of a race condition: two threads both increment a shared counter. The increment is not atomic — it compiles to three instructions (LOAD → ADD → STORE) and the scheduler can interrupt between any two of them.

static volatile int myglobal = 0;
#define ITERS 100000

void thread_a(void) {
    for (int i = 0; i < ITERS; i++) myglobal++;  /* NOT atomic */
    vga_printf("A done. myglobal = %d\n", myglobal);
}

void thread_b(void) {
    for (int i = 0; i < ITERS; i++) myglobal++;
    vga_printf("B done. myglobal = %d\n", myglobal);
}
/* Expected: 200000 — Actual: somewhere between 100000 and 200000 */

A mutex has two states: unlocked (0) and locked (1). The key requirement is that the test-and-set must be atomic — no other thread can sneak in between the check and the set. x86 provides the XCHG instruction which is implicitly atomic (it asserts LOCK# on the bus).

/* include/mutex.h */
typedef struct {
    volatile int  locked;     /* 0 = free, 1 = held */
    int           owner;      /* TID of holder (-1 if free) */
    int           waiters[MAX_PROCS]; /* blocked thread queue */
    int           nwaiters;
} mutex_t;

/* kernel/mutex.c */
static inline int atomic_xchg(volatile int *ptr, int val) {
    int old;
    __asm__ volatile("xchgl %0, %1"
        : "=r"(old), "+m"(*ptr)
        : "0"(val) : "memory");
    return old;
}

void mutex_lock(mutex_t *m) {
    while (atomic_xchg(&m->locked, 1) == 1) {
        /* Lock is held — add self to waiters and block */
        m->waiters[m->nwaiters++] = current_tid;
        proc_table[current_tid].state = PROC_BLOCKED;
        scheduler_yield();  /* give up the CPU */
    }
    m->owner = current_tid;
}

void mutex_unlock(mutex_t *m) {
    m->owner  = -1;
    m->locked =  0;
    /* Unblock first waiter if any */
    if (m->nwaiters > 0) {
        int tid = m->waiters[--m->nwaiters];
        proc_table[tid].state = PROC_READY;
    }
}

A semaphore generalises a mutex: the internal counter can be any non-negative integer, not just 0/1. semWait decrements the counter; if it would go negative the calling thread blocks. semSignal increments the counter and unblocks one waiter if any exist. This is the Dijkstra definition from Lecture 11.

/* include/semaphore.h */
typedef struct {
    volatile int  count;
    int           waiters[MAX_PROCS];
    int           nwaiters;
} semaphore_t;

void sem_init   (semaphore_t *s, int initial);
void sem_wait   (semaphore_t *s);   /* P / semWait / down */
void sem_signal (semaphore_t *s);   /* V / semSignal / up */

/* Producer-Consumer validation — kernel/shell.c */
#define BUF_SIZE 8
static int          buffer[BUF_SIZE];
static semaphore_t  sem_empty, sem_full, sem_mutex;

void producer_init(void) {
    sem_init(&sem_empty, BUF_SIZE); /* BUF_SIZE empty slots */
    sem_init(&sem_full,  0);        /* 0 full slots         */
    sem_init(&sem_mutex, 1);        /* binary mutex         */
}

Before entering Protected Mode the bootloader calls INT 0x15, EAX=0xE820 to query the BIOS memory map. Each call returns one entry describing a region of physical memory (usable RAM, reserved, ACPI, etc.) The results are written into a known address (e.g. 0x8000) where pmm_init() reads them later.

; In boot.asm — call before LGDT/CR0 (still in Real Mode)
detect_memory:
    mov  di, 0x8004        ; Write entries starting at 0x8004
    xor  ebx, ebx           ; EBX=0 to start iteration
    xor  bp,  bp            ; BP = entry count
.e820_loop:
    mov  eax, 0xE820
    mov  ecx, 24            ; 24-byte entry
    mov  edx, 0x534D4150    ; Magic: 'SMAP'
    int  0x15
    jc   .e820_done         ; CF set = error or end of list
    inc  bp
    add  di, 24
    test ebx, ebx
    jnz  .e820_loop
.e820_done:
    mov  [0x8000], bp      ; Store count at 0x8000

For 32 MB of RAM there are 32 MB / 4 KB = 8192 frames. The bitmap is 8192 bits = 1 KB — tiny. We store it as an array of uint32_t, using bit manipulation to test, set, and clear individual bits efficiently.

/* kernel/pmm.c */
#define FRAME_SIZE      4096
#define BITMAP_SIZE     (32 * 1024 * 1024 / FRAME_SIZE / 32)

static uint32_t bitmap[BITMAP_SIZE];  /* 1 bit per frame */
static uint32_t total_frames;
static uint32_t free_frames;

static inline void bitmap_set  (uint32_t f) { bitmap[f/32] |=  (1u << (f%32)); }
static inline void bitmap_clear(uint32_t f) { bitmap[f/32] &= ~(1u << (f%32)); }
static inline int  bitmap_test (uint32_t f) { return (bitmap[f/32] >> (f%32)) & 1; }

uint32_t pmm_alloc_frame(void) {
    for (uint32_t i = 0; i < total_frames; i++) {
        if (!bitmap_test(i)) {
            bitmap_set(i);
            free_frames--;
            return i * FRAME_SIZE;  /* physical address */
        }
    }
    return 0;  /* OOM */
}

void pmm_free_frame(uint32_t phys) {
    uint32_t frame = phys / FRAME_SIZE;
    bitmap_clear(frame);
    free_frames++;
}

uint32_t pmm_free_frames (void) { return free_frames;  }
uint32_t pmm_total_frames(void) { return total_frames; }

void pmm_init(void) {
    /* Start with all frames marked used */
    memset(bitmap, 0xFF, sizeof(bitmap));

    uint16_t   count   = *(uint16_t *)0x8000;
    e820_entry_t *map = (e820_entry_t *)0x8004;

    for (int i = 0; i < count; i++) {
        if (map[i].type != 1) continue;   /* type 1 = usable RAM */
        uint32_t start = (uint32_t)map[i].base;
        uint32_t len   = (uint32_t)map[i].length;
        /* Free frames in this region, skipping the first 1 MB + kernel */
        uint32_t first = (start < KERNEL_END) ? KERNEL_END : start;
        for (uint32_t a = first; a < start + len; a += FRAME_SIZE) {
            bitmap_clear(a / FRAME_SIZE);
            free_frames++;
        }
    }
    total_frames = (32 * 1024 * 1024) / FRAME_SIZE;
}

The 1 MB RAM disk is divided into fixed-size regions. All sizes are chosen to be round multiples of the 512-byte block size. The layout below uses 256-byte inodes and 512-byte data blocks.

/* include/fs.h */
#define FS_MAGIC        0x21213F5   /* SENG21213 magic */
#define BLOCK_SIZE      512
#define MAX_INODES      1024
#define INODE_DIRECT    8          /* 8 direct block pointers per inode */

typedef struct {
    uint32_t magic;
    uint32_t total_blocks;
    uint32_t total_inodes;
    uint32_t free_blocks;
    uint32_t free_inodes;
    uint32_t inode_table_off; /* byte offset of inode table */
    uint32_t data_off;        /* byte offset of first data block */
} superblock_t;

typedef struct {
    uint32_t size;                    /* file size in bytes */
    uint32_t blocks[INODE_DIRECT];    /* direct block indices */
    uint32_t block_count;
    uint8_t  type;                    /* 0=free 1=file 2=dir */
    char     name[28];               /* flat FS: name lives in inode */
} inode_t;

/* include/fs.h — public API */
void     fs_init    (void);
int      fs_open   (const char *name, int flags); /* returns fd or -1 */
int      fs_read   (int fd, void *buf, int n);
int      fs_write  (int fd, const void *buf, int n);
void     fs_close  (int fd);
int      fs_unlink (const char *name);
int      fs_ls     (inode_t *out, int max); /* fill array, return count */

/* Flags for fs_open */
#define O_RDONLY   0x01
#define O_WRONLY   0x02
#define O_CREAT    0x04   /* create if not exists */
#define O_TRUNC    0x08   /* truncate to zero on open */

/* Add to commands[] in kernel/shell.c */

static void cmd_ls(int argc, char *argv[]) {
    inode_t inodes[MAX_INODES];
    int n = fs_ls(inodes, MAX_INODES);
    vga_printf("%-24s %8s\n", "NAME", "SIZE");
    vga_puts  ("------------------------ --------\n");
    for (int i = 0; i < n; i++)
        vga_printf("%-24s %8u\n", inodes[i].name, inodes[i].size);
    vga_printf("%d file(s)\n", n);
}

static void cmd_write(int argc, char *argv[]) {
    /* write <filename> <text...> */
    if (argc < 3) { vga_puts("Usage: write <file> <text>\n"); return; }
    int fd = fs_open(argv[1], O_WRONLY | O_CREAT | O_TRUNC);
    if (fd < 0) { vga_puts("Cannot open file\n"); return; }
    for (int i = 2; i < argc; i++) {
        fs_write(fd, argv[i], strlen(argv[i]));
        if (i < argc - 1) fs_write(fd, " ", 1);
    }
    fs_close(fd);
}

seng21213-os/
├── boot/
│   └── boot.asm            # MBR + E820 memory detection
│   └── switch.asm          # context_switch() — PUSHAD/POPAD
├── kernel/
│   ├── kernel.c            # kernel_main() — initialises all subsystems
│   ├── shell.c             # Shell + all commands
│   ├── string.c            # memset / strlen / strcmp etc.
│   ├── process.c           # Process table (Stage 1)
│   ├── scheduler.c         # Round-Robin scheduler (Stage 1)
│   ├── idt.c               # IDT + PIC + PIT init (Stage 1)
│   ├── thread.c            # Kernel threads (Stage 2)
│   ├── mutex.c             # Blocking mutex (Stage 2)
│   ├── semaphore.c         # Counting semaphore (Stage 2)
│   ├── pmm.c               # Physical memory manager (Stage 3)
│   ├── ramdisk.c           # 1 MB RAM disk block device (Stage 4)
│   └── fs.c                # Inode file system (Stage 4)
├── drivers/
│   ├── vga/
│   │   └── vga.c
│   └── keyboard/
│       └── keyboard.c
├── include/
│   ├── kernel.h  vga.h  keyboard.h  io.h  shell.h  string.h
│   ├── process.h  scheduler.h  idt.h
│   ├── thread.h   mutex.h      semaphore.h
│   ├── pmm.h
│   └── ramdisk.h  fs.h
├── linker.ld
├── Makefile
├── run.sh
└── README.md

Green entries are new files you add at that stage. Black entries are from Stage 0.