Differences

This shows you the differences between two versions of the page.

--- kdp20260218-2 [May 13, 2026 at 18:36] – yanevskiv
+++ kdp20260218-2 [May 14, 2026 at 11:38] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
+# KDP Exam (2026-02-18) Question 2
+*The Roller Coaster Problem*. Assume there are $N$ passengers and $M$ cars in one roller coaster. Passengers alternate between walking around the amusement park and riding the roller coaster. One car can take at most $K$ passengers where $K < N$. Roller coaster ride can only begin if exactly $K$ passengers enter the roller coaster. Ensure that rides end in the order they began. Also ensure that passengers that waited longer to start their ride start earlier. Solve this problem using semaphroes.
+## Solution
+```c
+#define N ... /* passenger count */
+#define K ... /* car count */
+Sem mutex = 1;
+Sem canBoard = 0;
+Sem canLeave = 0;
+Sem allBoarded = 0;
+Sem allLeft = 0;
+int waitCount = 0;
+int rideCount = 0;
+void passenger() {
+    while (true) {
+        // ... walk around the amusement park ...
+        // Arrive at car
+        wait(mutex);
+        waitCount += 1;
+        if (waitCount >= K) {
+            signal(canBoard);
+        }
+        signal(mutex);
+        wait(canBoard);
+        // Enter the car
+        wait(mutex);
+        waitCount -= 1;
+        rideCount += 1;
+        if (rideCount < K) {
+            signal(canBoard);
+        } else {
+            signal(allBoarded);
+        }
+        signal(mutex);
+        // ... ride the roller coaster ...
+        // Leave the car
+        wait(canLeave);
+        wait(mutex);
+        rideCount -= 1;
+        if (rideCount > 0) {
+            signal(canLeave);
+        } else {
+            signal(allLeft);
+        }
+        signal(mutex);
+    }
+}
+void car() {
+    while (true) {
+        wait(allBoarded);
+        // ... do the ride ...
+        signal(canLeave);
+        wait(allLeft);
+    }
+}
+```