Critical Section


cache management

Tuesday,  04/07/15  10:32 AM

<post type=nerdy optional=yes>

Cache maintenance between multiple threads is a tricky business.

Consider a simple situation, a cache which contains items read from disk.  The basic thing we do with this cache is search for an item, and if not found we read the item and put it into the cache.  With one thread this is dirt simple:

  • Search cache for item, if not found:
    • Read item from disk
    • Put item in cache

With more than one thread, things go from simple to not simple.  Now the cache must be protected by a gate to serialize access (gates are also known as a “semaphores”).

For some reason under Windows these are not called gates or semaphores, they are called CriticalSections or Mutexes. Don’t get me started.

Okay, so the basic logic above now becomes (try 1):

  • Get cache gate
  • Search cache for item, if not found:
    • Read item from disk
    • Put item in cache
  • Free cache gate

Does this look right?  Well, if we leave the cache gated while reading from disk, we force all cache users to block on the disk read.  Not good.  So how about this (try 2):

  • Get cache gate
  • Search cache for item, if not found:
    • Free cache gate
    • Read item from disk
    • Get cache gate
    • Put item in cache
  • Free cache gate

Better, right?  This way we will only serialize cache access, not disk access.  That is probably the main reason we have multiple threads, so this is good.  But we do have a problem, what if two threads concurrently want the same item?  We could have the following timing:

___thread1

  • Get cache gate
  • Search cache for item, not found
  • Free cache gate -->
  • Read item from disk
     
  • Get cache gate
  • Put item in cache
  • Free cache gate -->  

___thread2

  • Blocks on cache gate
     
  • Get cache gate
  • Search cache for item, not found
  • Read item from disk again
  • Blocks on cache gate
     
  • Get cache gate
  • Put item in cache again
  • Free cache gate

Depending on the application, this could happen anywhere from "never" to "always".  If items are accessed more or less randomly "never" is probably a good approximation.  But if items are accessed more or less in sequence "always" is probably close.  For this case is there anything better we can do?

The crux of the problem is that thread2 doesn't know thread1 is already reading the item.  If it did, it could simply wait, then retrieve it from the cache, and life would be good.  So suppose we use this logic (try 3):

  • Get cache gate
  • Search cache for item, if not found:
    • Put "in progress" token for item in cache
    • Free cache gate
    • Read item
    • Get cache gate
    • Put item in cache, clear "in progress" token
  • If item "in progress":
    • Free cache gate
    • Delay
    • Loop up to top
  • Free cache gate

Of course the "in progress" token adds complexity.  But now the scenario above becomes:

___thread1

  • Get cache gate
  • Search cache for item, not found
  • Put "in progress" token in cache
  • Free cache gate -->
  • Read item from disk
     
  • Get cache gate
  • Put item in cache
  • Free cache gate -->

___thread2

  • Blocks on cache gate
       
     
  • Get cache gate
  • Search cache for item, returns "in progress" 
  • Delay ...  
  • Blocks on cache gate
     
  • Get cache gate
  • Search cache for item, returns "found"
  • Free cache gate

Much better…  A more complicated solution still would be to replace the delay with some kind of event.  In actual practice a simple delay and retry is probably sufficient.

</post>

Home
Archive
flight
About Me
W=UH
Email
RSS   OPML

Greatest Hits
Correlation vs. Causality
The Tyranny of Email
Unnatural Selection
Lying
Aperio's Mission = Automating Pathology
On Blame
Try, or Try Not
Books and Wine
Emergent Properties
God and Beauty
Moving Mount Fuji The Nest Rock 'n Roll
IQ and Populations
Are You a Bright?
Adding Value
Confidence
The Joy of Craftsmanship
The Emperor's New Code
Toy Story
The Return of the King
Religion vs IQ
In the Wet
the big day
solving bongard problems
visiting Titan
unintelligent design
the nuclear option
estimating in meatspace
second gear
On the Persistence of Bad Design...
Texas chili cookoff
almost famous design and stochastic debugging
may I take your order?
universal healthcare
entertainment
triple double
New Yorker covers
Death Rider! (da da dum)
how did I get here (Mt.Whitney)?
the Law of Significance
Holiday Inn
Daniel Jacoby's photographs
the first bird
Gödel Escher Bach: Birthday Cantatatata
Father's Day (in pictures)
your cat for my car
Jobsnotes of note
world population map
no joy in Baker
vote smart
exact nonsense
introducing eyesFinder
resolved
to space
notebooks
where are the desktop apps?