How exactly do semaphores work, especially when combined with sync/timeout?

Questions & Answers
1

I was writing some code using semaphores and realized that I wasn't sure I completely understand them.

Suppose I have something like this:

(define sema (make-semaphore 1))
(define user->id (make-hash (list (cons 'alice 1) (cons 'bill 2))))
(define id->user (make-hash (list (cons 1 'alice) (cons 2 'bill))))
(define (get-name id)    (hash-ref id->user id))
(define (get-id   name)  (hash-ref user->id name))

(define (add-user! name id)
  (call-with-semaphore sema
                       (thunk
                        (hash-set! user->id name id)
                        (hash-set! id->user id name))))

(add-user! 'charlie 3)
(get-name 2)
(get-id 'alice)

My understanding is that:

A. Racket is single-threaded and implements concurrency by periodically pausing the current thread and running a different one.
B. The semaphore ensures that if multiple threads want to call add-user! then they will take turns, thereby ensuring that the two hashes are always consistent.

The things I'm not sure about:

  1. Do I need to worry about get-name seeing an inconsistent state if it's running in thread A and the add-user! is happening in thread B?
  2. How exactly does this work? Does call-with-semaphore pause all other threads (or, rather, disable thread switching) while it finishes the protected block?
  3. If the answer to 1 is yes then I believe the solution is to use the semaphore in both the accessors and mutators, while being careful to avoid deadlock. Is this right?
  4. If the answer to 2 is yes then does the time spent in the protected block count against the duration of a sync/timeout in another thread?
1 Like
2

Your program will ensure mutual exclusion between different calls to add-user!. But the semaphore doesn't protect against anything that isn't checking it, so calls like get-name could run in between the two hash-set! calls. So the answer to 1 is "yes, you need to worry about that".

If you only have this one data structure that you're protecting, then just using the same semaphore for everything should be fine. If you have a more complex situation than that, then I highly recommend using multiple threads and communicating via channels, rather than sharing mutable data between threads.

2 Likes
3

Cool, thanks. So, in summary:

  • Semaphores do not disable thread switching
  • Therefore accessors and mutators must coordinate
  • Mutability = badness (this I knew, but the specific thing I'm working on is awkward to do without it)
  • Because threads can switch at (essentially) any time, a semaphore-protected block is not special in how much latency it generates as compared to any other thread

Do I have that correct?

4

Yes, that's all correct.

Mutation is fine; it's shared mutable data that's not fine. The way I'd do something like your example is have a thread that holds (and does not share) the mutable hash table, and then communicate with that thread via a channel to do things like add a user or query the table.

2 Likes