2
$\begingroup$

I'm trying to understand the algorithm for implementing semaphores on SMP system using test and set instruction described here: https://people.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf

(and a bunch of similar implementations on the web).

Locking semaphore looks like this:

void P(Semaphore s)
{
  Disable interrupts;
  while (ldl(s->lock) != 0 k !stc(s->lock, 1));
  if (s->count > 0) {
    s->count -= 1;
    s->lock = 0;
    Enable interrupts;
    return;
  }
  Add(s->q, current thread);
  s->lock = 0;
  sleep(); /* re-dispatch */
  Enable interrupts;
}

I have a number of questions about this. One is -- what is enabling and disabling of interrupts for? It seems that the whole reason we are using test and set is that interrupt disasbling is not feasible on SMP systems.
Then, what does the sleep() followed by enable interrupts mean? Does it mean that we do whole sleep with interrupts disabled? That can't be right as it defeats the purpose of sleeping. And if we first enable interrupts and then sleep, doesn't it mean that we have a possibility of missing a wakeup after lock is set to 0 but before we sleep?

$\endgroup$
1
$\begingroup$

The purpose of the spinlock is to prevent other cores from entering the critical section. The purpose of disabling interrupts is to prevent this core from re-entering the critical section.

The only way this core could try to re-acquire the semaphore is if an interrupt occurs and the interrupt handler needs the semaphore for some reason. Disabling interrupts prevents this from occurring.

As for the reason why sleep() is called after releasing the spinlock but before interrupts are enabled... well, that depends too much on the specifics of the operating system design to give a general answer.

The whole of the "waiting on the semaphore" operation should be atomic. That includes waiting on its queue and transitioning the thread from its "running" state to its "waiting" state. Presumably, that's what the call to sleep() is supposed to do.

You wonder if there's a possible race condition where this CPU releases the spinlock on the semaphore, then some other CPU signals the semaphore, then this cpu calls sleep(). That isn't necessarily a problem. If sleep() is written such that if it finds that the current thread is runnable it handles that case correctly, it won't cause a problem.

So why are interrupts disabled when you call sleep()? Some kernels are just designed that way, in that interrupts need to be disabled when you call into the scheduler. The call to sleep() may not actually "sleep"; it might just be whatever the scheduler has to do to make a thread sleep.

Alternatively, if there is a thread context switch hidden deep inside that call to sleep(), that may be where interrupts are re-enabled.

Ultimately, this code is designed to get the general idea across. How you would implement it in a real kernel would be like this, but this isn't necessarily drop-in code.

(Consider that load-linked/store-conditional instructions are spelled out in the example but there's no memory barrier operation on the spinlock release. That's a very specific ISA!)

$\endgroup$
  • $\begingroup$ thanks. Why do you need both the spinlock and disabling of the interrupts? Isn't spinlock going to cover both? $\endgroup$ – MK. Nov 6 '17 at 14:27
  • $\begingroup$ Please re-read the first two paragraphs of my answer. If you need further clarification, ask. $\endgroup$ – Pseudonym Nov 7 '17 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.