Good Evening,

Hi! I’m a bit confused about Chapter 28: Section Using Queues: Sleeping Instead Of Spinning

My first confusion is around lock and guard in:

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

guard is a lock guard protecting flag ensuring that modifications to flag are atomic. Is there reason a reason that both the guard and flag are needed?

Is

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

not sufficient? I’m at least having difficulty coming up with a way…

I think it’s because you need a flag or it’d be impossible to implement the if/else block in the lock function without it. In a sense, the if/else block is a critical section of it’s own. Is this summation correct?

Less Spinning Clarification

However, the time spent spinning is quite limited (just a few instructions inside the lock and unlock code, instead of the user-defined critical section), and thus this approach may be reasonable. if/else block

Okay, so I’m confused here because… We spin for less time because small section… user-defined sections will take longer…

or not you could enter the critical section

User Asked Question

Need to answer this question…

A question for the reader: What would happen if the release of the guard lock came after the park(), and not before?

Is this just after park, the

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

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; //acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 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)
        ; //acquire guard lock by spinning
    if (queue_empty(m->q))
        m->flag = 0; // let go of lock; no one wants it
    else
        unpark(queue_remove(m->q)); // hold lock
    // (for next thread!)
    m->guard = 0;
}

Sleep Forever Scenario

There’s this question…

Why would it sleep forever…

The subsequent park by the first thread would then sleep forever (potentially)

So, in what case would this sleep forever? Is it because of this scenario:

1. Thread 0 adds itself to the queue (queue_add(m->q, gettid()))
2. Releases the lock (m->guard = 0)
3. Time slice ends
4. Thread 1 Runs
5. Thread 1 calls lock
6. Thread 1 calls unlock
7. The queue pops of Thread 0
8. And then Thread 0 is woken up
9. And then thread 0 continues where it lefts off
10. Thread 0 left of at park
11. Thread 0 calls park

And because of this sequence, thread 0 is not in the queue and so it could never be woken up via unpark.

11. Goes to sleep
12. Not part of queue
13. And because it’s not par

Alternatives to setpark

atomically release the lock and dequeue the running thread.

How would this happen? How could the kernel atomically do operations? I had thought atomicity was made possible through the hardware? With a single processor, the kernel could clear interrupts and then restore it? But how about when there’s more than one? Would you add yet another lock?

typedef int my_lock_t;
static my_lock_t _queue_park_lock = 0;

#define SPINLOCK_ACQUIRE()                                    \
    do {                                                      \
        while (TestAndSet(&_queue_park_lock, 1) == 1) {       \
            ;                                                 \
        }                                                     \
    } while (0)

#define SPINLOCK_RELEASE() \
    _queue_park_lock = 0
    
    



void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; //acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1; // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        // Put a spin lock around guard and park?
        SPINLOCK_ACQUIRE();
        m->guard = 0;
        park();
    // release the lock
   SPINLOCK_RELEASE();
    }
}

But that doesn’t work as the problem isn’t with two threads calling m->guard and then calling park. It’s not really a critical section. The problem is with it being interrupted and then a subsequent thread calling unlock. Is there a mechanism that allows code blocks (not instructions) to be executed atomically? Google suggests that hardware transactional memory is the answer

In OSTEP, you state:

For simplicity, we will use the support provided by Solaris, in terms of two calls: park() to put a calling thread to sleep, and unpark(threadID) to wake a particular thread as designated by threadID. These two routines can be used in tandem to build a lock that puts a caller to sleep if it tries to acquire a held lock and wakes it when the lock is free.

And I just want to make sure I understand why you put threads to sleep. Every thread that is schedulable is awake and so when you attempt to lock it and the lock isn’t free, you: 1.) add it to the queue 2.) set the guard to 0 and finally, 3.) you put the thread to sleep via park

The queue serves two functions: 1.) threads waiting to acquire the lock a.) this is its main function 2.) deschedule threads that would only waste time slices by spinning a.) because these threads are asleep, they can’t be scheduled