Thread: Semaphore design in slab allocator

  1. #1
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    London, United Kingdom

    Semaphore design in slab allocator

    Hello everyone,

    I am currently working on implementing a slab allocator in C. Before I jump straight to my question, allow me to introduce the concept a little bit for those unfamiliar with it. A slab allocator is like a cache for objects (i.e. structs) that need to be allocated and deallocated very often, particularly in operating system design. In order to reduce the time it takes to malloc() memory for a specific struct, use it, and then free it every time, a slab allocator contains pre-allocated memory for an array of such structs and allocates them ALL when initializing the cache. When you want to allocate memory for an object in your main program, you simply ask the cache to give you a pointer to an already malloc-ed unused chunk, and call the constructor for your object to initialize the struct, via a function pointer in the cache.

    Now, my particular cache is made up of several lines (called slabs), and each slab is a fixed size array of memory chunks for user structs. The slabs are actually nodes in a linked list, since the cache can grow vertically (i.e. add or remove slabs) but not horizontally (i.e. all slabs have identical size arrays of chunks).

    One of the things I have to implement is multi-threading support, so I have a two level semaphore system. The first level is at the slab level. When the user requests a pointer from a slab, the slab lock is set and the cache has to "wait" for the lock to be removed before issuing another request for allocation on that slab. The second semaphore tier is at cache level. If the cache grows in no. of slabs or shrinks, due to previously used slabs being empty, the cache-level lock is set on, and no requests can be made to the cache while it is changing its size.

    In the second case, the user program has to wait until the lock for the cache is removed, while in the first the cache itself has to wait for a slab to finish allocation before issuing a new one.

    My question is, how exactly do you implement this wait for the semaphore to change in C? I know that there are specific sleep methods for different OS's however I would like to make this behavior as OS-independent as possible.

    I figure a dumb way to do it is to just wait in a loop continuously checking the lock flag until it changes, but that would be a waste of processor time.
    (i.e. while(slab_lock != 1); )

    I appreciate any ideas or design considerations for solving these issues.
    Thanks to everyone in anticipation!

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    There is no "independent" method. The only way to provide proper synchronization is to use the synchronization primitives provided by your OS and/or threading library.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Game Engine Design
    By IceDane in forum Game Programming
    Replies: 2
    Last Post: 01-17-2010, 02:47 PM
  2. Semaphore algorithm
    By erasm in forum C Programming
    Replies: 3
    Last Post: 09-20-2009, 11:04 AM
  3. allocator implementation
    By George2 in forum C++ Programming
    Replies: 4
    Last Post: 02-28-2008, 05:39 AM
  4. Semaphore Question
    By azamsharp1 in forum C Programming
    Replies: 4
    Last Post: 10-30-2005, 09:01 AM
  5. CreateSemaphore/ReleaseSemaphore
    By nrieger in forum Windows Programming
    Replies: 2
    Last Post: 08-03-2005, 06:57 AM