Critical Section

Archive: April 7, 2015

<<< April 6, 2015

Home

April 13, 2015 >>>


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>

 

Tuesday,  04/07/15  08:55 PM

Man is it *cold* out here today.  Brrr...  Too cold to ride.  Even too cold to think!  But not too cold to blog...

Deborah Harry, Tom Petty, and Ronnie SpectorHow great was this: Tom Petty backing Deborah Harry at the Whisky?  (I saw Alannah Myles there, does that count?)

So, Rand Paul is running for President.  "I am running for president to return our country to the principles of liberty and limited government."  Sounds good, but ... I just can't get excited about him.  I don't think he will be the GOP candidate.

In re Indiana: Tim Cook, end the hypocrisy.  "Tim Cook’s message [about Indiana] seems rather ironic in light of the fact that Apple willingly does business with some of the most virulently anti-gay nations on the planet."  This is the challenge when business leaders start staking out political views.  I wonder if Tim Cook will think this through?

Glenn Reynolds: You've probably breaking the lot right now.  "While a century or two ago nearly all crime was traditional common-law crime - rape, murder, theft and other things that pretty much everyone should know are bad - nowadays we face all sorts of 'regulatory crimes' in which intuitions of right and wrong play no role, but for which the penalties are high."  Ignorance of the law is not only a valid excuse, it's inevitable.

the Boneshaker Big WheelA cross between a penny-farthing and the Burning Man strandbeest: the Boneshaker Big Wheel.  Wow.  That's just about all I can say.

Only on the Internet: Science Babe takes down Food Babe.  "Hari's rule?  'If a third grader can't pronounce it, don't eat it.'  My rule?  Don't base your diet on the pronunciation skills of an eight-year-old."  Hehe.

baby elephant gets help crossing a roadHow did the baby elephant cross the road?  With help from two adult elephants.  Cuteness overload.

 

noone noticed

Tuesday,  04/07/15  09:04 PM

Very apropos considering my recent return:

"phew, noone really noticed you were gone"
Hehe

 

 
 

Return to the archive.

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?