Unsung SQLOS: linked lists

I’m slowly working towards some more juicy subjects again, but for the moment it is sensible to get fundamentals out of the way. The use of linked lists by SQL Server and SQLOS is a great place to start, because so much is built upon them. Grok this and you’re set for countless hours of fun.

From general exposure to SQLOS scheduling, many of us are familiar with concepts like “the worker is put on the runnable list”. At a high level this is simple to grasp, and the good news is that not much is hidden from us in the implementation detail. Nonetheless, it seems that it’s only systems programmers who deal with these details nowadays, but it’s still useful for the rest of us to get a chance to get comfortable with such internals.

Linked list implementation in SQLOS

A SQLOS doubly linked list follows a common Windows pattern based on a ListEntry structure. This is remarkably simple, containing only two pointer-sized members, i.e. taking up 16 bytes on x64:

  • flink (forward link) – a pointer to the next entry in the list
  • blink (backward link) – a pointer to the previous entry in the list

Continue reading “Unsung SQLOS: linked lists”