About This Project
This project focuses on building a lightweight user-level threading system from scratch without relying on the traditional pthreads library. Instead of depending on the operating system kernel, the implementation manages threads entirely in user space using a many-to-one threading model, where multiple user threads are mapped to a single kernel thread. This approach provides flexibility and efficiency but requires designing a custom scheduler and handling context switching manually. To achieve this, the system leverages the ucontext library to create and manage execution contexts. Each thread is assigned its own stack and execution state, allowing seamless switching between threads using functions such as getcontext(), makecontext(), and swapcontext(). A timer-based preemption mechanism is implemented using signals, enabling threads to be interrupted after a fixed time slice (100 ms) and rescheduled. This ensures that long-running threads do not monopolize CPU time while still allowing shorter tasks to yield control voluntarily. The project implements and compares two scheduling algorithms: Round Robin and Lottery Scheduling. The Round Robin scheduler follows a deterministic approach, assigning equal CPU time to each thread in a cyclic order. In contrast, the Lottery Scheduler introduces a probabilistic model where threads are assigned tickets representing their share of CPU time. Threads with more tickets have a higher chance of execution, enabling flexible and priority-based scheduling. A key highlight of this project is the experimental validation of fairness in Lottery Scheduling, inspired by Waldspurger’s research. By running threads with different ticket ratios (e.g., 1:2, 1:3, etc.), the results demonstrate that CPU allocation closely follows the assigned proportions over time. As execution continues, the observed performance converges toward the theoretical fairness ratio, confirming the effectiveness of probabilistic scheduling. Overall, this project provides a deep understanding of thread management, scheduling algorithms, context switching, and signal handling at the system level. It highlights the trade-offs between deterministic and probabilistic scheduling while demonstrating how operating system concepts can be implemented at the user level.
Key Features
- Custom user-level threading library (many-to-one model) without pthreads
- Manual context switching using ucontext APIs
- Preemptive scheduling using timer interrupts (SIGVTALRM)
- Round Robin scheduler with fixed time slicing
- Lottery Scheduler with ticket-based probabilistic scheduling
- Dynamic thread creation with independent stacks (8KB per thread)
- Ready queue management for scheduling decisions
- Signal-driven execution control and thread preemption
- Experimental validation of fairness in Lottery Scheduling
- Comparative analysis of Round Robin vs Lottery scheduling
