Project 4: POSIX Message Queue Priority Dispatcher

Implement a priority dispatcher using POSIX message queues.

Quick Reference

Attribute Value
Difficulty Level 3 (Advanced)
Time Estimate 1 Week
Main Programming Language C (Alternatives: Rust)
Alternative Programming Languages Rust
Coolness Level Level 3 (Genuinely Clever)
Business Potential Level 3 (Service & Support Model)
Prerequisites C programming, basic IPC familiarity, Linux tools (strace/ipcs)
Key Topics POSIX MQ, priorities, backpressure, mq_notify

1. Learning Objectives

By completing this project, you will:

  1. Build a working IPC-based system aligned with Stevens Vol. 2 concepts.
  2. Implement robust lifecycle management for IPC objects.
  3. Handle errors and edge cases deterministically.
  4. Document and justify design trade-offs.
  5. Benchmark or validate correctness under load.

2. All Theory Needed (Per-Concept Breakdown)

POSIX Message Queues (mq_*) and Priority Scheduling

Fundamentals

POSIX message queues provide kernel-managed message passing with explicit message boundaries and priorities. Unlike pipes, which are byte streams, message queues deliver complete messages up to a configured maximum size. Each message has an associated priority, and the kernel delivers messages in priority order. This makes POSIX MQs ideal for systems that need structured, ordered IPC without reinventing framing.

A POSIX MQ is created with mq_open() and named with a string like /myqueue. It lives in a dedicated filesystem namespace (often /dev/mqueue). Attributes such as maximum message size and queue depth are configured via mq_attr. Calls like mq_send and mq_receive are blocking by default but can be made non-blocking. Like files, queues have permissions, and they can be unlinked with mq_unlink() while still open by active processes.

Deep Dive into the Concept

The kernel enforces a finite capacity for each queue: both the total number of messages and the maximum size of each message. If the queue is full, mq_send() blocks unless O_NONBLOCK is set, in which case it returns EAGAIN. This behavior is a built-in backpressure mechanism. When the queue is empty, mq_receive() blocks unless O_NONBLOCK is set. Understanding these blocking semantics is crucial for building responsive systems. Many designs pair MQs with mq_notify or select/poll to avoid blocking in a single-threaded server.

Priority ordering is another deep feature. POSIX MQs define higher numeric values as higher priority, and delivery is ordered first by priority, then FIFO within the same priority. This is not just a convenience; it lets you implement urgent control messages alongside bulk data without building separate channels. However, priority can also cause starvation: a constant stream of high-priority messages can prevent low-priority messages from ever being processed. A well-designed system uses a bounded priority scheme and monitoring to avoid starvation.

Another important detail is the difference between named and unnamed queues in POSIX. POSIX MQs are always named; they are not created as anonymous objects like pipes. This means you must handle naming collisions (O_CREAT | O_EXCL) and cleanup (mq_unlink). If you crash without unlinking, the queue persists and can cause subsequent runs to fail or inherit old configuration. This persistence is both a feature and a foot-gun. It is one of the core differences from pipes and demonstrates why lifecycle semantics matter in IPC design.

How this fits on projects

POSIX MQs are the core of the priority dispatcher project and a baseline for benchmarking against System V MQs. Their explicit message semantics also influence higher-level RPC protocols.

Definitions & key terms

  • Message queue -> Kernel buffer that stores discrete messages.
  • Priority -> Integer controlling message delivery order.
  • mq_attr -> Attributes struct controlling size/depth.
  • Backpressure -> Blocking behavior when queue is full.

Mental model diagram (ASCII)

Producers -> [ POSIX MQ ] -> Consumer
            (priority ordered)

POSIX message queue flow

How it works (step-by-step, with invariants and failure modes)

  1. Create queue with mq_open and attributes.
  2. Producers send messages with priority.
  3. Consumer receives highest-priority message available.
  4. If queue fills, producers block or get EAGAIN.
  5. Cleanup with mq_close and mq_unlink.

Failure modes: failing to unlink queues, starvation of low-priority messages, exceeding size limits.

Minimal concrete example

mqd_t q = mq_open("/demo", O_CREAT|O_RDWR, 0600, &attr);
unsigned prio = 10;
mq_send(q, "hello", 5, prio);
char buf[32];
unsigned out_prio;
mq_receive(q, buf, sizeof(buf), &out_prio);


**Common misconceptions**

- "POSIX MQs are just like pipes." -> They are message-based with priorities.
- "Queues disappear when a process exits." -> They persist until `mq_unlink`.
- "Priority only affects scheduling." -> It can cause starvation if misused.

**Check-your-understanding questions**

1. What happens when the queue is full and `mq_send` is called?
2. How does priority affect delivery order?
3. Why might you need `O_EXCL` with `mq_open`?

**Check-your-understanding answers**

1. It blocks or returns `EAGAIN` if non-blocking.
2. Highest priority messages are delivered first; FIFO within same priority.
3. To avoid accidental reuse of stale queues from previous runs.

**Real-world applications**

- Real-time command dispatchers.
- High-priority alert channels.

**Where you’ll apply it**

- In this project: §3.2 Functional Requirements, §6 Testing Strategy.
- Also used in: [P06-mq-benchmark.md](P06-mq-benchmark.md).

**References**

- `man 7 mq_overview`, `man 3 mq_open`.
- Stevens, "UNP Vol 2" Ch. 7.

**Key insights**

- POSIX MQs give you message boundaries and priorities, but you must manage lifecycle and limits.

**Summary**

POSIX message queues are the simplest kernel-supported way to send structured messages with priority. They are perfect for dispatchers and control planes.

**Homework/Exercises to practice the concept**

1. Create a queue with `msg_max=4` and demonstrate backpressure.
2. Send mixed-priority messages and observe ordering.
3. Crash a sender without `mq_unlink`, then observe queue persistence.

**Solutions to the homework/exercises**

1. Send 5 messages without a receiver and observe blocking or `EAGAIN`.
2. Use priorities 1 and 10; note that priority 10 arrives first.
3. List `/dev/mqueue` and clean with `mq_unlink`.


---

## 3. Project Specification

### 3.1 What You Will Build

Implement a priority dispatcher using POSIX message queues.

### 3.2 Functional Requirements

1. **Requirement 1**: Multiple producers send messages with priority
2. **Requirement 2**: Dispatcher always handles highest priority first
3. **Requirement 3**: Queue attributes and limits are configurable

### 3.3 Non-Functional Requirements

- **Performance**: Must handle at least 10,000 messages/operations without failure.
- **Reliability**: IPC objects are cleaned up on shutdown or crash detection.
- **Usability**: CLI output is readable with clear error codes.

### 3.4 Example Usage / Output

```text
./dispatcher &
./send --prio 10 urgent
./send --prio 1 bulk


### 3.5 Data Formats / Schemas / Protocols

Message struct: {u32 id; u8 prio; u32 len; bytes payload}.

### 3.6 Edge Cases

- Queue full returns EAGAIN
- Starvation of low priority
- mq_unlink cleanup

### 3.7 Real World Outcome

You will have a working IPC subsystem that can be run, traced, and tested in a reproducible way.

#### 3.7.1 How to Run (Copy/Paste)

```bash
make
./run_demo.sh


#### 3.7.2 Golden Path Demo (Deterministic)

```bash
./run_demo.sh --mode=golden


Expected output includes deterministic counts and a final success line:

```text
OK: golden scenario completed


#### 3.7.3 Failure Demo (Deterministic)

```bash
./run_demo.sh --mode=failure


Expected output:

```text
ERROR: invalid input or unavailable IPC resource
exit=2


---

## 4. Solution Architecture

### 4.1 High-Level Design


Client/Producer -> IPC Layer -> Server/Consumer

Client to IPC layer to server flow

4.2 Key Components

Component Responsibility Key Decisions
IPC Setup Create/open IPC objects POSIX vs System V choices
Worker Loop Send/receive messages Blocking vs non-blocking
Cleanup Unlink/remove IPC objects Crash safety

4.3 Data Structures (No Full Code)

struct message {
  int id;
  int len;
  char payload[256];
};


### 4.4 Algorithm Overview

**Key Algorithm: IPC Request/Response**
1. Initialize IPC resources.
2. Client sends request.
3. Server processes and responds.
4. Cleanup on exit.

**Complexity Analysis:**
- Time: O(n) in number of messages.
- Space: O(1) per message plus IPC buffer.

---

## 5. Implementation Guide

### 5.1 Development Environment Setup

```bash
sudo apt-get install build-essential


### 5.2 Project Structure


project-root/
├── src/
├── include/
├── tests/
├── Makefile
└── README.md

Project root directory layout

5.3 The Core Question You’re Answering

“How do you enforce priority scheduling at the IPC level?”

5.4 Concepts You Must Understand First

  • IPC object lifecycle (create/open/unlink)
  • Blocking vs non-blocking operations
  • Error handling with errno

5.5 Questions to Guide Your Design

  1. What invariants guarantee correctness in this IPC flow?
  2. How will you prevent resource leaks across crashes?
  3. How will you make the system observable for debugging?

5.6 Thinking Exercise

Before coding, sketch the IPC lifecycle and identify where deadlock could occur.

5.7 The Interview Questions They’ll Ask

  1. Why choose this IPC mechanism over alternatives?
  2. What are the lifecycle pitfalls?
  3. How do you test IPC code reliably?

5.8 Hints in Layers

Hint 1: Start with a single producer and consumer.

Hint 2: Add logging around every IPC call.

Hint 3: Use strace or ipcs to verify resources.

5.9 Books That Will Help

Topic Book Chapter
IPC fundamentals Stevens, UNP Vol 2 Relevant chapters
System calls APUE Ch. 15

5.10 Implementation Phases

Phase 1: Foundation (2-4 hours)

Goals:

  • Create IPC objects.
  • Implement a minimal send/receive loop.

Tasks:

  1. Initialize IPC resources.
  2. Implement basic client and server.

Checkpoint: Single request/response works.

Phase 2: Core Functionality (4-8 hours)

Goals:

  • Add error handling and cleanup.
  • Support multiple clients or concurrent operations.

Tasks:

  1. Add structured message format.
  2. Implement cleanup on shutdown.

Checkpoint: System runs under load without leaks.

Phase 3: Polish & Edge Cases (2-4 hours)

Goals:

  • Add deterministic tests.
  • Document behaviors.

Tasks:

  1. Add golden and failure scenarios.
  2. Document limitations.

Checkpoint: Tests pass, behavior documented.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Blocking mode blocking vs non-blocking blocking Simpler for first version
Cleanup manual vs automated explicit cleanup Avoid stale IPC objects

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate helpers message encode/decode
Integration Tests IPC flow client-server round trip
Edge Case Tests Failure modes missing queue, full buffer

6.2 Critical Test Cases

  1. Single client request/response works.
  2. Multiple requests do not corrupt state.
  3. Failure case returns exit code 2.

6.3 Test Data

Input: “hello” Expected: “hello”

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Not cleaning IPC objects Next run fails Add cleanup on exit
Blocking forever Program hangs Add timeouts or non-blocking mode
Incorrect message framing Corrupted data Add length prefix and validate

7.2 Debugging Strategies

  • Use strace -f to see IPC syscalls.
  • Use ipcs or /dev/mqueue to inspect objects.

7.3 Performance Traps

  • Small queue sizes cause frequent blocking.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add verbose logging.
  • Add a CLI flag to toggle non-blocking mode.

8.2 Intermediate Extensions

  • Add request timeouts.
  • Add a metrics report.

8.3 Advanced Extensions

  • Implement load testing with multiple clients.
  • Add crash recovery logic.

9. Real-World Connections

9.1 Industry Applications

  • IPC services in local daemons.
  • Message-based coordination in legacy systems.
  • nfs-utils - Uses RPC and IPC extensively.
  • systemd - Uses multiple IPC mechanisms.

9.3 Interview Relevance

  • Demonstrates system call knowledge and concurrency reasoning.

10. Resources

10.1 Essential Reading

  • Stevens, “UNP Vol 2”.
  • Kerrisk, “The Linux Programming Interface”.

10.2 Video Resources

  • Unix IPC lectures from OS courses.

10.3 Tools & Documentation

  • man 7 ipc, man 2 for each syscall.

11. Self-Assessment Checklist

11.1 Understanding

  • I can describe IPC object lifecycle.
  • I can explain blocking vs non-blocking behavior.
  • I can reason about failure modes.

11.2 Implementation

  • All functional requirements are met.
  • Tests pass.
  • IPC objects are cleaned up.

11.3 Growth

  • I can explain design trade-offs.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Basic IPC flow works with correct cleanup.
  • Error handling returns deterministic exit codes.

Full Completion:

  • Includes tests and deterministic demos.
  • Documents trade-offs and limitations.

Excellence (Going Above & Beyond):

  • Adds performance benchmarking and crash recovery.