IPC & Synchronization (C++ Only)

This assignment covers inter-process communication, threads, and synchronization primitives. C++ only (compiled with g++ -std=c++20 -pthread).

Your program reads the first line of input to determine which part to solve: PIPE, BUFFER, RWLOCK, or POOL.

---

Part 1: Pipe Pipeline Simulator (25 points)

Simulate data flowing through a chain of Unix-style pipe stages. Each stage applies a transformation to the lines of text.

Supported Commands

| Command | Description | |---------|-------------| | upper | Convert all characters to uppercase | | lower | Convert all characters to lowercase | | sort | Sort lines lexicographically (ascending) | | uniq | Remove consecutive duplicate lines | | head N | Keep only the first N lines | | tail N | Keep only the last N lines | | grep PATTERN | Keep lines containing PATTERN (case-sensitive substring) | | wc -l | Output a single number: the count of input lines | | reverse | Reverse the order of lines | | sed s/OLD/NEW/ | Replace first occurrence of OLD with NEW in each line |

Input Format

PIPE
<N lines of input data>
<line 1>
...
<line N>
<M commands>
<cmd 1>
...
<cmd M>

Output Format

The final result after piping through all stages. If the result is empty, produce no output.

Example

Input:

PIPE
5
banana
apple
cherry
apple
banana
3
sort
uniq
upper

Output:

APPLE
BANANA
CHERRY

---

Part 2: Producer-Consumer Bounded Buffer (25 points)

Simulate the classic producer-consumer problem with a bounded buffer.

Input Format

BUFFER
<buffer_capacity>
<num_events>
<time> <thread_id> <P item | C>
...

• P item — produce (add item to back of buffer)
• C — consume (remove item from front of buffer)

Rules

1. Process events in input order. Events at the same timestamp are processed in input order.
2. Produce: If the buffer is full, the thread blocks and joins a produce-wait queue (FIFO).
3. Consume: If the buffer is empty, the thread blocks and joins a consume-wait queue (FIFO).
4. After each successful consume, check the produce-wait queue: if the first waiter can now produce, wake it (the woken produce completes at the same timestamp). Repeat until the queue is empty or the buffer is full again.
5. After each successful produce, check the consume-wait queue: if the first waiter can now consume, wake it (the woken consume completes at the same timestamp). Repeat until the queue is empty or the buffer is empty again.

Output Format

One line per completed event:

<time> <thread_id> produced <item> [<comma-separated buffer contents>]
<time> <thread_id> consumed <item> [<comma-separated buffer contents>]

Example

Input:

BUFFER
2
5
0 T1 P apple
0 T2 P banana
1 T3 P cherry
1 T4 C
1 T5 C

Trace:

• Time 0: T1 produces apple (buffer: [apple]). T2 produces banana (buffer: [apple, banana]).
• Time 1: T3 tries to produce cherry — buffer full, blocks. T4 consumes apple (buffer: [banana]) — T3 wakes up and produces cherry (buffer: [banana, cherry]). T5 consumes banana (buffer: [cherry]).

Output:

0 T1 produced apple [apple]
0 T2 produced banana [apple, banana]
1 T4 consumed apple [banana]
1 T3 produced cherry [banana, cherry]
1 T5 consumed banana [cherry]

---

Part 3: Reader-Writer Lock Simulator (25 points)

Simulate reader-writer lock semantics with writer preference (prevents writer starvation).

Input Format

RWLOCK
<num_requests>
<time> <thread_id> <R|W> <duration>
...

Rules

1. Multiple readers can hold the lock simultaneously.
2. Writers need exclusive access (no other readers or writers).
3. Writer preference: When any writer is waiting, no new reader may start (prevents writer starvation).
4. Requests are processed in input order. Requests that cannot proceed immediately join a FIFO wait queue.
5. When a writer finishes: check the wait queue. If the next waiter is a reader, start it and all consecutive readers after it (up to the next waiting writer). If the next waiter is a writer, start that writer.
6. When all active readers finish: start the next waiting writer.

Output Format

One line per request, in order of start time (ties broken by thread_id lexicographic order):

<thread_id> <reading|writing> <start_time> to <end_time>

Example

Input:

RWLOCK
4
0 T1 R 3
0 T2 R 2
1 T3 W 2
1 T4 R 1

Trace:

• Time 0: T1 and T2 start reading (no writers waiting).
• Time 1: T3 requests write — readers active, waits. T4 requests read — writer T3 waiting (writer pref), waits.
• Time 2: T2 finishes. T1 still reading, T3 still waits.
• Time 3: T1 finishes. T3 starts writing (3 to 5).
• Time 5: T3 finishes. T4 starts reading (5 to 6).

Output:

T1 reading 0 to 3
T2 reading 0 to 2
T3 writing 3 to 5
T4 reading 5 to 6

---

Part 4: Thread Pool Scheduler (25 points)

Simulate a thread pool with N worker threads processing tasks from a shared FIFO queue.

Input Format

POOL
<num_workers>
<num_tasks>
<arrival_time> <task_id> <duration>
...

Tasks in input are sorted by arrival time.

Rules

At each timestamp, process in this order:

1. New tasks arriving at this time are added to the back of the queue.
2. Workers that complete tasks at this time become idle.
3. Idle workers pick up tasks from the front of the queue. When multiple workers are idle, the lowest worker ID picks first.

Output Format

One line per task, in order of start time (ties broken by worker ID):

<task_id> W<worker_id> <start_time> <end_time>

Example

Input:

POOL
2
4
0 T1 3
0 T2 2
3 T3 1
3 T4 2

Trace:

• Time 0: T1, T2 queued. W0 picks T1 (0-3), W1 picks T2 (0-2).
• Time 2: W1 finishes T2, idles.
• Time 3: T3, T4 queued. W0 finishes T1. W0 picks T3 (3-4), W1 picks T4 (3-5).

Output:

T1 W0 0 3
T2 W1 0 2
T3 W0 3 4
T4 W1 3 5