Scheduling & Concurrency (Mini Assignment)

This mini assignment covers scheduling and concurrency concepts. You may use Python or C++.

---

Part 1: CPU Scheduler (50 points)

Implement a CPU Scheduling Simulator supporting:

1. FCFS (First-Come, First-Served)
2. SJF (Shortest Job First - non-preemptive)
3. RR (Round Robin with configurable quantum)

Input Format

<algorithm> [quantum if RR]
<number of processes>
<process_id> <arrival_time> <burst_time>
...

Output Format

<execution order as space-separated process IDs>
Average Waiting Time: <value>
Average Turnaround Time: <value>

---

Part 2: Traffic Intersection (50 points)

Simulate a 4-way traffic intersection using semaphores for synchronization.

Cars arrive from 4 directions (N, S, E, W) and must safely cross without collisions. You must use semaphores to coordinate access to the intersection.

Concurrency Model

• Each car is a separate thread
• Use a semaphore to control which axis (N/S or E/W) has the green light
• Cars on the same axis can cross simultaneously (semaphore allows multiple cars)
• Cars on perpendicular axes must wait (mutual exclusion between axes)

Rules

1. Opposite directions share green lights: N/S cars cross together, E/W cars cross together
2. Round-robin scheduling: The light alternates between N/S axis and E/W axis
3. Batch processing: All waiting cars on the current green axis cross simultaneously in one time unit
4. Priority: N/S axis has priority when cars from both axes are waiting at the same time
5. Timing: Each crossing takes exactly 1 time unit. If cars arrive at time T, the earliest they can cross is time T+1

Implementation Hints

Python: Use threading.Semaphore and spawn a thread per car.

import threading
intersection_sem = threading.Semaphore(1)

def car_thread(car_id, direction, arrival_time):
    # Acquire semaphore, cross, release
    pass

C++: Use <semaphore> (C++20) or <mutex> with <thread>.

#include <semaphore>
#include <thread>
std::binary_semaphore intersection_sem(1);

void car_thread(std::string car_id, char direction, int arrival) {
    // acquire, cross, release
}

Algorithm

1. Spawn a thread for each car at its arrival time
2. Use semaphores to ensure only one axis crosses at a time
3. Within an axis, multiple cars cross simultaneously
4. Alternate between N/S and E/W axes (N/S has priority if both waiting)
5. Output crossing events in the order they occur

Input Format

<number of car arrivals>
<timestamp> <car_id> <direction>
...

Note: Cars are given in order of arrival timestamp. Within the same timestamp, they appear in input order.

Output Format

For each car, output when it crosses (in crossing order):

<car_id> crosses at <timestamp>

Example

Input:

6
0 C1 N
0 C2 S
0 C3 E
2 C4 W
2 C5 N
3 C6 E

Trace:

• Time 0: C1(N), C2(S), C3(E) arrive
• Time 1: Light goes green for N/S. C1 and C2 cross (N/S has priority)
• Time 2: C4(W), C5(N) arrive. Light goes green for E/W. C3 crosses
• Time 3: C6(E) arrives. Light goes green for N/S. C5 crosses
• Time 4: Light goes green for E/W. C4 and C6 cross

Output:

C1 crosses at 1
C2 crosses at 1
C3 crosses at 2
C5 crosses at 3
C4 crosses at 4
C6 crosses at 4