Email: akshayjo@andrew.cmu.edu | Phone: 412-999-8546 | LinkedIn
The Dynamic Memory Allocator project for 15-513 focused on designing a custom heap manager that
implements malloc, free, realloc, and calloc
operations efficiently to support varied allocation sizes and patterns.
To minimize fragmentation and accelerate block selection, the allocator uses segregated free lists that categorize free blocks into multiple size classes, enabling near-constant-time best-fit searches within the smallest suitable list.
Small-size classes up to 96 bytes are grouped in 16 byte increments, and dedicated “mini blocks” of 32 bytes eliminate footer overhead, boosting memory utilization for tiny allocations.
On each allocation request, the size is rounded up to 16 byte alignment; the allocator probes the corresponding free list using a best-fit policy to minimize leftover space. If no block fits, the heap is extended by 4 KB and large remainders are split and reinserted into their appropriate lists.
When freeing memory, blocks are immediately coalesced with adjacent free neighbors to reduce external fragmentation and then returned to the correct segregated list for rapid reuse.
Benchmarking with the standard mdriver suite demonstrated an average memory utilization of
74.4% and throughput up to 12,800 kilo-operations per second on a 3.0 GHz CPU, outperforming naive
first-fit and next-fit allocators.
A comprehensive heap checker validated invariants—such as correct header/footer pairing, alignment guarantees, and proper coalescing—ensuring robustness under diverse workloads.
The Tiny Linux Shell implements a minimal Unix command interpreter with support for both built-in and external commands, providing job control semantics similar to standard shells. It enables users to manage foreground and background jobs, respond to signals such as Ctrl-C and Ctrl-Z, and prevent zombie processes by correctly reaping child processes.
Upon startup, the shell configures prompt display and installs signal handlers for SIGINT, SIGTSTP, SIGCHLD, SIGTTIN, and SIGTTOU to manage job control reliably. The core of the shell is a read–eval loop that prints a prompt, reads a line from stdin, parses it into tokens, and dispatches either a built-in function or forks a child process to execute an external program.
Built-in commands (`quit`, `jobs`, `bg`, `fg`) execute within the shell process and manipulate an internal linked list job table that tracks job IDs, PIDs, and states (foreground, background, stopped). The `jobs` command lists all active jobs, while `bg` and `fg` resume stopped jobs in background or foreground by sending SIGCONT to the appropriate process group.
Non-built-in commands are executed by forking a child process, placing it in its own process group, and invoking `execve` to load the desired executable. Input and output redirection is supported by opening specified files and duplicating file descriptors via `dup2()` before `execve`, ensuring the child’s stdin and stdout are correctly routed.
A SIGCHLD handler reaps terminated or stopped children using `waitpid` with `WNOHANG|WUNTRACED`, updating job states and avoiding zombie processes. SIGINT and SIGTSTP handlers forward interrupts and stop signals to the foreground job’s process group, allowing the shell itself to remain responsive. Critical sections that modify the job list are protected by blocking all signals with `sigprocmask` to prevent race conditions between the main loop and asynchronous handlers.