wakeup/waiting race in a lock?

Question

I am reading through the OSTEP book by prof.Remzi http://pages.cs.wisc.edu/~remzi/OSTEP/

I could only partially understand how the following code results in wakeup/waiting race condition.(The code is taken from the books chapter. http://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf

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

park() sys call puts a calling thread to sleep, and unpark(threadID) is used to wake a particular thread as designated by threadID.

Now if thread1 hold the lock by setting the m->flag to 1. If the thread2 comes in to acquire the lock, it fails. So the else case is executed, and the thread2 is added to queue, but-assume-if before park() sys call is made, thread2 is scheduled out and thread1 is given the timeslice. If thread1 releases the lock,unlock function tries to call unpark syscall(queue is non empty), since thread2 is in the queue. But the thread2 did not call park() sys call, it just got added to queue.

So the question is
1) what does the thread1's unpark() returns, just a error saying threadID not found?(os specific)
2) what happens to the lock flag ? it was supposed to be passed between the subsequent threads which called the lock routine, freeing the lock only when no more lock contention.

The book says thread2 will sleep for ever. But my understanding is any subsequent threads contesting for the locks will sleep forever,say thread3 tries to acquire lock at later time, because the the lock is never freed by thread1 during the unlock call.

My understanding is most probably wrong because the book was very specific in pointing out thread2 sleeping forever. Or am just reading too much in the example and my understanding is correct?!!! and there is a deadlock?

Grouse

Answer 1

Mailed this question to prof.Remzi and got a reply from him !!!. Just posting the reply here.

Prof.Remzi's reply:

good questions!

I think you basically have it right.

unpark() will return (and perhaps say that the threadID was not sleeping); in this implementation, the lock is left locked, and thread2 will sleep forever, and as you say all subsequent threads trying to acquire the lock won't be able to.

Grouse

Answer 2

I think your understanding is correct. I think the unpark() will still return(but did not work normally). Since the thread2 never sleeps the lock held by thread1 will not free. The subsequent threads like thread3,...threadN will still add to the queue and sleep. Also, the thread2 has already been removed from the queue and I would say it is in kind of 'sleep' forever.

Amalekite