Work through the following systems-programming exercises. State the memory and concurrency model you assume before writing pseudocode. ### Part 1: Stack Machine and Reverse Polish Notation Design an evaluator for integer Reverse Polish Notation with literals and basic binary operators. Reject malformed input, division by zero, unknown tokens, and extra operands. Then add named macros whose bodies are token sequences. Define whether macros may call other macros and how recursion is detected. #### What This Part Should Cover - Operand-stack invariants and validation - Operator arity and integer-division semantics - Macro expansion or invocation strategy - Cycle detection and bounded expansion ### Part 2: Lock-Free SPSC Queue Design a bounded single-producer, single-consumer queue. Explain the ownership of read and write indices, full and empty detection, publication order, and the required atomic memory ordering. #### What This Part Should Cover - A ring-buffer representation - Why one producer and one consumer simplify synchronization - Release/acquire publication - Wraparound and capacity accounting ### Part 3: False Sharing Explain how false sharing can hurt the queue even when the producer and consumer update different variables. Show how you would lay out the indices and justify any padding or alignment. #### What This Part Should Cover - Cache-line invalidation rather than logical data races - Separation of independently written counters - The danger of assuming a universal cache-line size ### Part 4: Cross-Thread Pool Allocator Orders are allocated on one thread and freed on another. Design a pool allocator that reduces per-order allocation while keeping ownership and reclamation safe. #### What This Part Should Cover - Slabs or blocks and a free-object representation - A remote-free path back to the owning allocator - ABA, lifetime, and shutdown concerns - When a lock-free design is not worth its complexity ### What a Strong Answer Covers A strong answer distinguishes algorithmic correctness from language-specific memory-order guarantees. It starts with simple safe designs, identifies the exact contention path, and adds lock-free mechanisms only where their invariants can be defended. ### Follow-up Questions - How would macros accept arguments? - What changes for a multi-producer queue? - How would you test the allocator under forced thread interleavings?