# 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;
    }
}
```