How is semaphore queue protected with multiple threads

Question

In one of the interviews I was asked...

Wait(semaphore sem) {                           
   DISABLE_INTS
   sem.val--
   if (sem.val < 0){
      add thread to sem.L
      block(thread)
    }
ENABLE_INTS

The above is the semaphore wait implementation (copied from other thread). How is the queue sem.L protected when multiple threads try to enqueue (when they fail to get the lock) ? Do we take lock before updating the queue ?

Answer 1

This is an implementation for a system with only a single core. Concurrency is managed by disabling interrupts during critical sections. That's what the "DISABLE_INTS" and "ENABLE_INTS" are in that code.

Unless you were interviewing for a position developing multi-tasking operating system code for single-core systems, it's a strange question to ask. Perhaps the interviewer was expecting you to ask questions about the code and see if you could understand under what circumstances this would make sense.

Conflict can only occur with code running on this core or another core. Since there's only one core, the only possible conflict is with code running on this care. That would require a context switch.

Context switches come in two forms, voluntary and involuntary. A voluntary context switch occurs when code explicitly asks for one. This code doesn't ask for a context switch, so that's not an issue. An involuntary context switch can only be triggered by an interrupt, and this code disables interrupts in its critical section. This was a typical way "locks" were implemented in kernel code for single core systems.