Question

Consider the two types of lock implementations based on atomic test&set() functions: one with fully busy wait, another with limited busy wait on a guard variable. Now show an execution trace with three threads (T1, T2, T3) that the CPU is not as busy in the “better” solution as in the “naïve” solution. No spamming please

Answer 1

Lock implementation with fully spinning based on atomic testAndset functions
=======================================
void init() {
T1 = 0;
}

void lock() {
while (TestAndSet(&T1, 1) == 1)
yield();
}

void unlock() {
T1 = 0;
}
In above lock implmentation, primitive yield()
which a thread can call when it wants to give up the CPU and let another
thread run. A thread can be in one of three states (running, ready,
or blocked); yield is simply a system call that moves the caller from the
running state to the ready state, and promotes another thread to
running. Thus, the yielding process essentially deschedules itself.

limited busy wait on a guard variable
======================================

typedef struct __lock_t {
int T1;
int guard;
queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
m->T1 = 0;
m->guard = 0;
queue_init(m->q);
}

void lock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1);
if (m->T1 == 0) {
m->T1 = 1; // lock is acquired
m->guard = 0;
} else {
queue_add(m->q, gettid());
m->guard = 0;
park();
}
}

void unlock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1);
if (queue_empty(m->q))
m->T1 = 0;
else
unpark(queue_remove(m->q));
m->guard = 0;
}

In above lock(), when a thread can not acquire
the lock (it is already held), by calling the gettid() function gets the thread ID of the
current thread, set guard to 0, and yield the CPU.