Differences

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

--- kdp20260110-1 [May 13, 2026 at 16:17] – yanevskiv
+++ kdp20260110-1 [May 14, 2026 at 11:38] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
+# KDP Midterm (2026-01-10) Question 1
+Write and explain the *Fine grain ticket algorithm* implemented with $\text{FA}$ opeartion. If we replaced $\text{FA}$ with $\text{TS}$ (test-and-set) operation implemented in the following way, would it be possible to implement a fine-grained solution? If yes, implement it. Is the critical section entry fair? Why / why not?
+```c
+bool TS(bool lock)
+{
+    atomic {
+        bool initial = lock;
+        lock = true;
+        return initial;
+    }
+}
+```
+## Solution
+$\text{FA}$ operation stands for "fetch-and-add". It's implemented in the following way.
+```c
+int FA(int& var, int by)
+{
+    atomic {
+        int old = var;
+        var += by;
+        return old;
+    }
+}
+```
+Fine-grained ticket algorithm implements "lock" and "unlock" sections in the following way. This also guarantees FIFO ordering of entry. Thus the lock is called "fair".
+```c
+#define N 5 /* Number of threads */
+shared int ticket = 0;
+void thread(int id)
+{
+    while (true) {
+        // lock
+        int number = FA(ticket, 1);
+        while (number != ticket)
+            skip();
+        // ... critical section ...
+        // unlock
+        tikcet += 1;
+    }
+}
+```
+The following is a *fine grain critical section* using $\text{TS}$. It's called "test-and-test-and-set". This avoids lock contentiont that the naive "test-and-set" implementation has. However, threads can enter the critical section in any order. Some threads may have to wait arbitrarily long on the lock because. This is called "starvation". Because starvation is possible on this lock it's considered "unfair".
+```c
+#define N 5 /* number of threads */
+shared bool lock = false;
+void thread(int id)
+{
+    while (true) {
+        // lock
+        do {
+            while (lock)
+                skip();
+        } while (!TS(lock));
+        // ... critical section ...
+        // unlock
+        lock = false;
+    }
+}
+```