Operating Systems Course - xv6 Kernel Development & Concurrent Systems

Student: Swarnadip Kar
Roll Number: 12342210
Institution: Indian Institute of Technology Bhilai
Course: CSL301 - Operating Systems
Academic Year: 2025-2026
Email: swarnadip.kr@gmail.com
GitHub: https://github.com/Swarnadip-Kar

---

Overview

This repository contains comprehensive coursework from the Operating Systems course at IIT Bhilai, with dual focus on xv6 kernel development and concurrent systems programming. The work demonstrates practical implementation of core OS concepts including process management, memory management, file systems, multithreading, and synchronization primitives.

The repository includes:

• 12+ substantial xv6 kernel modifications with custom system calls
• Extensive multithreading and synchronization implementations
• Classical concurrency problems solved using POSIX threads
• Scheduling algorithm replacements and page replacement policies
• Comprehensive LaTeX documentation for all implementations

---

Repository Structure

.
├── Assignments/                    # Take-home assignments
│   ├── Assignment 1/              # System calls and process control
│   ├── Assignment 2/              # Process information retrieval
│   ├── Assignment 3/              # Priority-based scheduling
│   └── 2025:XX:XX - .../         # Memory API, thread programming
│
├── LAB1-LAB12/                    # Weekly laboratory work
│   ├── LAB1-4/                    # Process basics and memory concepts
│   ├── LAB5/                      # Memory introspection system calls
│   ├── LAB6/                      # Virtual memory and paging
│   ├── LAB7/                      # Page replacement algorithms (FIFO, LRU)
│   ├── LAB8/                      # Multithreading fundamentals
│   ├── LAB9/                      # Semaphores and mutexes
│   ├── LAB10/                     # Barrier synchronization and deadlock
│   ├── LAB11/                     # Advanced synchronization patterns
│   └── LAB12/                     # Advanced kernel features
│
├── xv6-public/                    # Modified xv6 kernel source
├── 1) LATEX FILES/                # Professional documentation
├── OStep Code/                    # OSTEP textbook implementations
├── LAB EXAM Prep/                 # Lightswitch and synchronization patterns
└── Experiments/                   # Virtual memory experiments

---

Major Implementations

Assignment 1: Per-Process Flag System Calls

Implemented setflag(int) and getflag(void) system calls demonstrating complete kernel modification workflow.

Modified Files: proc.h, syscall.h, syscall.c, sysproc.c, user.h, usys.S

Key Concepts: System call interface design, kernel-user boundary crossing, process control block modification.

---

Assignment 2: Process Information Retrieval

Implemented pinfo(int pid, struct proc_info *info) system call for retrieving process metadata with safe concurrent access.

Implementation Highlights:

• Created procinfo.h defining struct proc_info (PID, name, state, size)
• Implemented get_proc_info_kernel() with proper spinlock usage
• Process state conversion (RUNNING, SLEEPING, ZOMBIE, etc.)
• Safe kernel-to-user space data copying

Test Programs: pinfo.c (interactive query), testproc.c (spawns 5 processes for testing)

Concurrency Control: Proper acquire/release of ptable.lock preventing race conditions during process table traversal.

---

Assignment 3: Static Priority Scheduling

Replaced xv6's round-robin scheduler with priority-based scheduling (lower value = higher priority).

Scheduler Redesign:

void scheduler(void) {
    for (;;) {
        acquire(&ptable.lock);

        // Linear scan for highest priority runnable process
        struct proc *highest_priority_p = 0;
        int highest_priority = 1000;

        for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
            if (p->state == RUNNABLE && p->priority < highest_priority) {
                highest_priority = p->priority;
                highest_priority_p = p;
            }
        }

        if (highest_priority_p != 0) {
            // Context switch to selected process
            c->proc = highest_priority_p;
            switchuvm(highest_priority_p);
            highest_priority_p->state = RUNNING;
            swtch(&(c->scheduler), highest_priority_p->context);
        }

        release(&ptable.lock);
    }
}

Dynamic Priority Control: setpriority(int) system call allows processes to modify their scheduling priority.

Testing: prioritytest.c spawns 5 children with priorities 10-50, demonstrating preemptive priority scheduling.

---

Assignment 4: Multithreading and Divide-and-Conquer

Implemented parallel algorithms using POSIX threads for performance comparison.

Problems Solved:

• Parallel matrix multiplication with thread pools
• Multi-threaded merge sort with work distribution
• Thread synchronization for result aggregation
• Performance benchmarking: sequential vs parallel execution

Key Learnings:

• Thread creation and management (pthread_create, pthread_join)
• Work partitioning strategies
• Cache locality considerations
• Amdahl's Law verification in practice

---

LAB 5: Memory Introspection System Calls

Implemented three system calls for memory analysis:

1. numvp() - Virtual Pages Count

return (p->sz + PGSIZE - 1) / PGSIZE + 1;  // +1 for stack guard

2. numpp() - Physical Pages Count

for (uint a = 0; a < p->sz; a += PGSIZE) {
    pte = walkpgdir(p->pgdir, (void*)a, 0);
    if (pte && (*pte & PTE_P))
        count++;
}

3. getptsize() - Page Table Memory Overhead

int count = 1;  // Outer page directory
for (int i = 0; i < NPDENTRIES; i++)
    if (p->pgdir[i] & PTE_P)
        count++;  // Each present inner page table

Understanding Demonstrated: x86 two-level paging, virtual-to-physical translation, page table structure.

---

LAB 7: Page Replacement Algorithms

FIFO Implementation

Kernel Modifications:

• Extended struct proc with int pages[MAX_PAGES] and page_count
• Modified allocuvm() for FIFO eviction logic
• On page fault: evict oldest page (index 0), shift queue, append new page

User Simulation: mytest.c with reference string [0,1,2,3,4,1,5,0,6,1,2,7,3,8,4]

Belady's Anomaly Testing: Tested with frame sizes 3, 4, 5 to observe page fault behavior.

LRU Implementation

Enhanced Tracking:

struct frameinfo {
    uint va;
    pte_t *pte;
    uint last_used;  // Timestamp from global ticks
};

Eviction Strategy: Scan frames for minimum last_used, evict oldest accessed page.

Performance: LRU demonstrated improved hit ratios compared to FIFO for locality-heavy workloads.

---

LAB 8: Multithreading Fundamentals

Programs Implemented:

Q1: Thread Creation and Basic Synchronization

• Multiple threads accessing shared counter
• Demonstration of race conditions
• Fixed version using mutex locks

Q2: Thread Arguments and Return Values

• Passing parameters to thread functions
• Collecting results from multiple threads
• Proper memory management for thread data

Q3: Thread Pools for Parallel Computation

• Fixed-size thread pool implementation
• Work queue with producer-consumer pattern
• Load balancing across threads

Q4: Thread Priorities and Scheduling

• Setting thread priorities using pthread_attr_setschedparam
• Real-time scheduling policies (FIFO, RR)
• Priority inversion demonstration

Q5: Thread-Local Storage

• Using __thread keyword for thread-private data
• Avoiding false sharing in multi-threaded programs

Platform Considerations:

• Separate implementations for Linux and macOS
• Handling differences in thread attribute initialization
• Conditional compilation for platform-specific features

---

LAB 9: Semaphores and Synchronization Primitives

Implementations:

1. Producer-Consumer Problem

sem_t empty, full;
pthread_mutex_t mutex;

void* producer(void* arg) {
    while(1) {
        produce_item();
        sem_wait(&empty);
        pthread_mutex_lock(&mutex);
        // Add to buffer
        pthread_mutex_unlock(&mutex);
        sem_post(&full);
    }
}

void* consumer(void* arg) {
    while(1) {
        sem_wait(&full);
        pthread_mutex_lock(&mutex);
        // Remove from buffer
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);
        consume_item();
    }
}

2. Readers-Writers Problem

• Reader Preference: Multiple readers can access simultaneously, writers wait
• Writer Preference: Writers get priority, readers may starve
• Fair Solution: FIFO queue for both readers and writers

Lightswitch Pattern:

typedef struct {
    int count;
    sem_t mutex;
    sem_t room_empty;
} Lightswitch;

void lightswitch_lock(Lightswitch *ls) {
    sem_wait(&ls->mutex);
    ls->count++;
    if (ls->count == 1)
        sem_wait(&ls->room_empty);  // First reader locks
    sem_post(&ls->mutex);
}

void lightswitch_unlock(Lightswitch *ls) {
    sem_wait(&ls->mutex);
    ls->count--;
    if (ls->count == 0)
        sem_post(&ls->room_empty);  // Last reader unlocks
    sem_post(&ls->mutex);
}

3. Bounded Buffer with Semaphores

• Fixed-size circular buffer
• empty semaphore: tracks free slots
• full semaphore: tracks filled slots
• Mutex for buffer access mutual exclusion

4. Multiplex Semaphore

• Limits concurrent access to N threads (e.g., database connection pool)
• Semaphore initialized to N
• Demonstrates resource throttling

---

LAB 10: Barrier Synchronization and Deadlock

1. Barrier Implementation

typedef struct {
    int count;
    int threshold;
    pthread_mutex_t mutex;
    pthread_cond_t cv;
} Barrier;

void barrier_wait(Barrier *b) {
    pthread_mutex_lock(&b->mutex);
    b->count++;
    if (b->count == b->threshold) {
        b->count = 0;
        pthread_cond_broadcast(&b->cv);
    } else {
        pthread_cond_wait(&b->cv, &b->mutex);
    }
    pthread_mutex_unlock(&b->mutex);
}

Use Case: Parallel iterative algorithms where all threads must complete one phase before proceeding.

2. Dining Philosophers Problem

Deadlock Version:

// Each philosopher picks up left fork, then right fork
// Circular wait leads to deadlock
void* philosopher(void* arg) {
    while(1) {
        think();
        pthread_mutex_lock(&forks[left]);
        pthread_mutex_lock(&forks[right]);  // DEADLOCK HERE
        eat();
        pthread_mutex_unlock(&forks[right]);
        pthread_mutex_unlock(&forks[left]);
    }
}

Deadlock-Free Solutions Implemented:

• Resource Ordering: Odd philosophers pick right fork first, even pick left first
• Limit Diners: Allow only N-1 philosophers to attempt eating simultaneously
• Timeout with Retry: Use pthread_mutex_timedlock() and retry on failure

3. Deadlock Detection

• Resource allocation graph construction
• Cycle detection algorithm
• Wait-for graph analysis

4. Reader-Writer Locks (rwlock)

• Custom implementation using mutex and condition variables
• Multiple readers, exclusive writer
• Fairness guarantees to prevent writer starvation

---

LAB 11: Advanced Synchronization Patterns

1. Thread Pool with Work Stealing

• Each thread has a local work queue
• Idle threads steal work from busy threads
• Lock-free queue operations using atomic operations

2. Condition Variable Patterns

// Producer
pthread_mutex_lock(&mutex);
while (buffer_full)
    pthread_cond_wait(&not_full, &mutex);
add_to_buffer();
pthread_cond_signal(&not_empty);
pthread_mutex_unlock(&mutex);

// Consumer
pthread_mutex_lock(&mutex);
while (buffer_empty)
    pthread_cond_wait(&not_empty, &mutex);
remove_from_buffer();
pthread_cond_signal(&not_full);
pthread_mutex_unlock(&mutex);

3. Double-Checked Locking for Lazy Initialization

if (singleton == NULL) {
    pthread_mutex_lock(&lock);
    if (singleton == NULL) {
        singleton = create_singleton();
    }
    pthread_mutex_unlock(&lock);
}
return singleton;

4. Monitor Pattern

• Encapsulation of shared data with synchronization
• Condition variables for waiting on state changes
• Automatic mutual exclusion for all operations

5. Parallel Prefix Sum (Scan)

• Barrier-based parallel algorithm
• Demonstrates work-efficient parallel computation
• O(log n) depth with O(n) work

---

LAB 12: Advanced Kernel Features

Two-Strike Ctrl+C Exit

Concept: Process requires two consecutive Ctrl+C presses to terminate.

Implementation:

• Extended struct proc with twostrike_mode and strike_count
• Modified consoleintr() in console.c to track strikes
• First Ctrl+C: Warning message, increment counter
• Second Ctrl+C: Set p->killed = 1
• System call twostrike(int enabled) to enable/disable mode

Use Case: Prevents accidental termination of critical processes.

Simplified ls Command

User-space implementation using stat(), opendir(), readdir():

• Basic listing
• Long format with permissions, owner, size, timestamp

Combined cp/mv Utility

Single program behaving as both copy and move:

• Detects mode from argv[0] or first argument
• Move: rename() syscall (atomic), fallback to copy+unlink
• Preserves file permissions via stat()

Inode-Based File System Simulation

In-memory file system with metadata:

• Inode structure with creator ID, timestamp, description
• create_file() and delete_file() operations
• Resource management (inode allocation, data block bitmap)

---

Concurrency Deep Dive: Problems and Solutions

Classical Synchronization Problems Solved

1. Producer-Consumer (Bounded Buffer)

• Problem: Coordinate producers and consumers sharing fixed-size buffer
• Solution: Two semaphores (empty/full) + mutex for buffer access
• Variants: Multiple producers/consumers, priority producers

2. Readers-Writers

• Problem: Allow multiple readers or single writer, never both
• Reader Preference: Readers never wait if another reader is active (writer starvation)
• Writer Preference: Writers get priority (reader starvation)
• Fair Solution: FIFO queue-based approach

3. Dining Philosophers

• Problem: 5 philosophers, 5 forks, need 2 forks to eat, avoid deadlock
• Solutions Implemented:
  • Resource ordering (break circular wait)
  • Limit concurrent diners (N-1 philosophers)
  • Asymmetric solution (odd/even different strategies)

4. Cigarette Smokers Problem

• Problem: 3 smokers, each missing one ingredient, agent provides 2 ingredients
• Solution: Using condition variables to signal specific smoker
• Learning: Demonstrates need for condition variables over semaphores

5. Sleeping Barber

• Problem: Barber sleeps when no customers, customers wait or leave if chairs full
• Solution: Semaphores for waiting room and barber synchronization
• Real-world: Models service queue systems

Deadlock Analysis

Necessary Conditions for Deadlock:

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait

Prevention Strategies Implemented:

• Resource Ordering: Global order for lock acquisition
• All-or-Nothing: Acquire all resources atomically or none
• Timeout and Retry: pthread_mutex_timedlock()
• Banker's Algorithm: Safe state verification before allocation

Detection Algorithms:

• Wait-for graph construction
• Cycle detection using DFS
• Resource allocation matrix analysis

---

Technical Skills

Kernel Development:

• System call implementation end-to-end
• Process and memory management internals
• Scheduler design and replacement
• Safe concurrent access to shared kernel structures
• Interrupt handling and console I/O

Concurrent Systems Programming:

• POSIX threads (pthreads) API mastery
• Mutex locks, semaphores, condition variables
• Barrier synchronization and monitors
• Deadlock prevention, detection, and recovery
• Race condition identification and elimination
• Thread-safe data structure design

Systems Programming:

• Low-level C programming (pointers, memory management)
• x86 architecture understanding (paging, context switching)
• Debugging with GDB and QEMU
• POSIX API (process control, file I/O, threading)

Performance Analysis:

• Parallel speedup measurement
• Amdahl's Law application
• Lock contention analysis
• Cache coherence considerations

---

Building and Testing

Prerequisites

# Ubuntu/Debian
sudo apt-get install build-essential qemu-system-x86 gdb

# For threading programs
sudo apt-get install libc6-dev

# For LaTeX
sudo apt-get install texlive-full python3-pygments

Building xv6

cd xv6-public
make clean
make
make qemu        # Run in QEMU
make qemu-nox    # Text-only mode

Testing in xv6 Shell

$ pinfo 1           # Process info
$ prioritytest      # Priority scheduling
$ memtest           # Memory statistics
$ twostriketest     # Two-strike exit
$ mytest            # Page replacement

Compiling Threading Programs

# Linux
cd LAB8  # or LAB9, LAB10, LAB11
gcc -pthread -o program program.c
./program

# macOS (if using named semaphores)
gcc -o program program.c
./program

Compiling Documentation

cd "1) LATEX FILES/LAB Assignments/[assignment_name]"
pdflatex -shell-escape main.tex

---

Key Learnings and Insights

Kernel Programming:

• System calls bridge user and kernel space with careful validation
• Kernel concurrency requires spinlocks, not regular mutexes
• Page tables enable virtual memory isolation between processes
• Scheduling policies dramatically affect system responsiveness

Concurrency:

• Race conditions are subtle and non-deterministic
• Always lock data, not code sections
• Deadlock requires all four conditions; breaking any one prevents it
• Condition variables require predicate loops (while, not if)
• Semaphores count, mutexes protect

Performance:

• Parallel programming doesn't always mean faster execution
• Lock contention can negate parallelism benefits
• Fine-grained locking increases complexity but improves concurrency
• Cache line bouncing is a major performance killer

---

Documentation

All assignments include comprehensive LaTeX reports with:

• Implementation details with annotated code snippets
• Technical explanations of design decisions
• Execution screenshots and output verification
• Performance analysis where applicable
• Analysis of trade-offs and limitations

Generated PDFs follow academic formatting standards with syntax highlighting via the minted package.

---

Academic Integrity

This repository contains original work completed during coursework at IIT Bhilai (2025-2026). All implementations were developed independently based on course materials, lectures, and textbook readings (OSTEP, xv6 book).

Code demonstrating classical synchronization problems draws from well-established algorithmic patterns documented in operating systems literature, with custom implementations and testing harnesses.

---

Contact

Swarnadip Kar
B.Tech. Computer Science and Engineering
Indian Institute of Technology Bhilai
Roll Number: 12342210

Email: swarnadip.kr@gmail.com
GitHub: https://github.com/Swarnadip-Kar

---

Last Updated: February 11, 2026