Project 4: Queue Systems

Build FIFO queues and a task scheduler that demonstrates fairness and throughput.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 1 week
Language C (Alternatives: Rust, Go)
Prerequisites Projects 1-3
Key Topics FIFO ordering, scheduling, throughput, bounded queues

1. Learning Objectives

By completing this project, you will:

  1. Implement queue operations with O(1) enqueue/dequeue.
  2. Compare circular buffer vs linked list queues.
  3. Build a task scheduler using queues.
  4. Analyze fairness and latency trade-offs.

2. Theoretical Foundation

2.1 Core Concepts

  • FIFO discipline: First-in, first-out ensures fairness.
  • Circular buffer: Uses array indices modulo capacity to avoid shifting.
  • Backpressure: Bounded queues apply pressure when full.
  • Scheduling: Queues model real-world job dispatch systems.

2.2 Why This Matters

Queues underpin operating systems, network buffers, message brokers, and batch systems. Understanding how to keep them O(1) is essential for systems performance.

2.3 Historical Context / Background

Classic OS schedulers and networking stacks rely on FIFO queues to enforce fairness and predictable behavior.

2.4 Common Misconceptions

  • “Queues are just lists”: A list implementation may be O(n) per dequeue.
  • “Capacity doesn’t matter”: Bounded queues change system behavior dramatically.

3. Project Specification

3.1 What You Will Build

  • A circular-buffer queue.
  • A linked-list queue.
  • A task scheduler simulator with multiple priority queues.

3.2 Functional Requirements

  1. Implement enqueue/dequeue/peek/is_empty/is_full.
  2. Support dynamic resizing for the array queue.
  3. Build a scheduler that takes tasks with durations and priorities.
  4. Provide metrics: average wait time, throughput.

3.3 Non-Functional Requirements

  • Performance: O(1) enqueue/dequeue.
  • Reliability: Proper handling of full/empty.
  • Usability: Metrics printed after each run.

3.4 Example Usage / Output

$ ./queue_scheduler
Queue capacity: 8
Enqueue task A(3), B(1), C(2)
Dispatch order: A, B, C
Average wait: 1.3s
Throughput: 2.0 tasks/sec

3.5 Real World Outcome

Run the scheduler and you see each task enter the queue with a timestamp. The program prints dispatch order and wait times. In priority mode, you see separate queues and how low-priority tasks still get service (round-robin across queues).

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐     ┌──────────────────┐     ┌────────────────┐
│ Queue Impl   │────▶│ Scheduler Engine │────▶│ Metrics Output │
└──────────────┘     └──────────────────┘     └────────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Circular queue Fast FIFO Head/tail wrap indices
Linked queue Alternative impl Node allocation per task
Scheduler Dispatch logic FIFO vs priority levels

4.3 Data Structures

typedef struct {
    char id[16];
    int duration_ms;
    int priority;
} Task;

typedef struct {
    Task* data;
    size_t capacity;
    size_t size;
    size_t head;
    size_t tail;
} CircularQueue;

4.4 Algorithm Overview

Key Algorithm: Circular Enqueue/Dequeue

  1. Enqueue at tail, increment modulo capacity.
  2. Dequeue from head, increment modulo capacity.

Complexity Analysis:

  • Time: O(1) enqueue/dequeue
  • Space: O(n) queue storage

5. Implementation Guide

5.1 Development Environment Setup

clang -Wall -Wextra -g -o queue_scheduler src/*.c

5.2 Project Structure

project-root/
├── src/
│   ├── queue.c
│   ├── scheduler.c
│   └── main.c
├── tests/
│   └── test_queue.c
└── Makefile

5.3 The Core Question You’re Answering

“How can I guarantee fairness in task processing while keeping operations O(1)?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Circular buffer indexing
  2. Queue invariants (head/tail)
  3. Scheduling metrics (wait time, throughput)

5.5 Questions to Guide Your Design

  1. Will the queue be bounded or dynamically grow?
  2. How will you represent priorities?
  3. How do you compute average wait time?

5.6 Thinking Exercise

Simulate a queue of size 4 with 5 enqueues and 3 dequeues. Track head/tail indices by hand.

5.7 The Interview Questions They’ll Ask

  1. “How do you implement a queue with O(1) operations?”
  2. “Why use a circular buffer instead of shifting elements?”
  3. “How would you prevent starvation in a priority queue?”

5.8 Hints in Layers

Hint 1: Track size separately You can differentiate full vs empty by storing size.

Hint 2: Resize carefully If you grow the array, copy in FIFO order starting at head.

5.9 Books That Will Help

Topic Book Chapter
Queues CLRS Ch. 10
Scheduling Operating Systems Concepts Ch. 5

5.10 Implementation Phases

Phase 1: Foundation (2 days)

Goals:

  • Circular queue operations
  • Basic tests

Tasks:

  1. Implement enqueue/dequeue.
  2. Add full/empty checks.

Checkpoint: Queue passes unit tests for wraparound.

Phase 2: Core Functionality (3 days)

Goals:

  • Scheduler logic
  • Metrics

Tasks:

  1. Add task struct and enqueue tasks.
  2. Compute wait times on dispatch.

Checkpoint: Scheduler prints dispatch order and metrics.

Phase 3: Polish & Edge Cases (2 days)

Goals:

  • Priority queues
  • Dynamic resizing

Tasks:

  1. Add multiple queues per priority.
  2. Implement resize for array queue.

Checkpoint: Priority scheduling still processes low-priority tasks.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Queue backing Circular array, linked list Circular array O(1) and cache-friendly
Priority model Single queue, multiple queues Multiple queues Clear fairness control

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Queue ops wraparound
Integration Tests Scheduler mix of durations
Edge Case Tests Full/empty dequeue empty

6.2 Critical Test Cases

  1. Wraparound: enqueue 4, dequeue 2, enqueue 2.
  2. Resize: grow capacity when full.
  3. Priority scheduling: verify non-starvation.

6.3 Test Data

Tasks: A(3), B(1), C(2), D(5)

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Head/tail confusion Lost tasks Track size and modulo
Resize bug Order wrong Copy in FIFO order
Starvation Low priority never runs Round-robin across queues

7.2 Debugging Strategies

  • Print head/tail/size after each operation.
  • Trace task IDs on enqueue/dequeue.

7.3 Performance Traps

  • Using memmove on every dequeue destroys O(1) guarantees.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a deque (double-ended queue).
  • Add peek at arbitrary index.

8.2 Intermediate Extensions

  • Implement a bounded blocking queue (single-threaded simulation).
  • Add weighted round-robin scheduling.

8.3 Advanced Extensions

  • Simulate M/M/1 queueing model and compare metrics.
  • Add persistent logging and replay.

9. Real-World Connections

9.1 Industry Applications

  • OS schedulers: CPU ready queues.
  • Message brokers: FIFO message queues.
  • RabbitMQ: queue semantics in brokers.
  • Linux kernel: run queues.

9.3 Interview Relevance

  • Queue implementation and scheduling trade-offs are interview staples.

10. Resources

10.1 Essential Reading

  • CLRS - queues and linked lists
  • Operating Systems Concepts - scheduling basics

10.2 Video Resources

  • “Scheduling Algorithms” - OS lectures

10.3 Tools & Documentation

  • perf: https://perf.wiki.kernel.org/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain FIFO vs LIFO.
  • I can implement a circular buffer.
  • I can explain fairness in scheduling.

11.2 Implementation

  • Queue operations are O(1).
  • Scheduler metrics are correct.

11.3 Growth

  • I can extend to priority scheduling.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Working queue with O(1) operations.
  • Basic scheduler demo.

Full Completion:

  • Priority queues and metrics.

Excellence (Going Above & Beyond):

  • Blocking queue or queueing model simulation.

This guide was generated from DATA_STRUCTURES_FROM_FIRST_PRINCIPLES.md. For the complete learning path, see the parent directory README.