On in-kernel dependencies

EDIT 2012/12/16: Removed unneeded interdependencies and updated naming conventions.

So far, I have described the various kernel components in a picture in which they are roughly independent, only quickly mentioning what depends on what. In reality, of course, the situation is more complex, and dependencies determine in which order kernel components shall be started. This post aims at determining said order.

Raw data about kernel components interdependencies

Let’s list the various dependencies of each kernel component and explain why each is needed.

InterruptManager
  • MemAllocator (same as above)
  • ProcessManager (same as above)
  • RPCManager (to trigger asynchronously interrupt-bound signals)
  • Scheduler (needs to perform context switches)
IOPortManager
  • MemAllocator (same as above)
  • ProcessManager (same as above)
MemAllocator
  • RAMManager (to allocate process memory and management structures)
  • PagingManager (to map allocated memory into processes’ address space)
  • ProcessManager (same as above)
MMIOManager
  • MemAllocator (same as above)
  • ProcessManager (same as above)
  • PagingManager (to map memory-mapped registers into a process’ virtual address space)
PagingManager
  • RAMManager (to allocate management structures)
  • ProcessManager (same as above)
ProcessManager
  • MemAllocator (to allocate management structures for a variable number of processes and insulators)
  • RPCManager (to communicate with user-mode insulators and notify them when processes are spawned, destroyed, and updated)
RAMManager
  • ProcessManager (same as above)
RPCManager
  • MemAllocator (same as above)
  • ProcessManager (to know when processes are spawned, destroyed, and updated)
  • Scheduler (to spawn threads within the processes that have received RPC calls)
Scheduler
  • InterruptManager (to receive and process clock interrupts)
  • IOPortManager, MMIOManager (to set up the clock for preemptive multitasking and control other CPU cores)
  • MemAllocator (same as above)
  • ProcessManager (same as above)
  • RPCManager (to exchange information with other scheduling-related system components)

Analysis and conclusions

It is easy to point out that everything depends on MemAllocator and ProcessManager, and that those should as such be started as early in the kernel initialization process as possible. However, MemAllocator and ProcessManager mutually depend on each other, so one must necessarily give up on some functionality until the other is started. Which should be started first ?

Since ProcessManager has a vital need for MemAllocator in order to allocate management structures whereas MemAllocator only needs ProcessManager after the kernel is loaded and begins to start user-mode processes, it appears to me that MemAllocator should be started first. Following MemAllocator’s own chain of dependencies, we get the following scenario :

  1. RAMManager is started
  2. PagingManager is started
  3. MemAllocator is started
  4. ProcessManager is started, gives MemAllocator, RAMManager, PagingManager access to its functionnality

At this point, IOPortManager and MMIOManager have everything they need to be initialized and should thus be started. This leaves us with three kernel components to start : RPCManager, Scheduler, and InterruptManager. Since RPCManager and InterruptManager both fully depend on Scheduler to be of any use while Scheduler can run a subset of its functionality (context switching and thread management) without them, Scheduler will have to be started first. Finally, InterruptManager depends on RPCManager while the reverse is not true, so we get this final ordering :

  1. RAMManager is started
  2. PagingManager is started
  3. MemAllocator is started
  4. ProcessManager is started, gives MemAllocator, RAMManager, PagingManager access to its functionality
  5. IOPortManager and MMIOManager are started, in any order.
  6. Scheduler is started
  7. RPCManager is started, gives ProcessManager and Scheduler access to its functionality
  8. InterruptManager is started, gives Scheduler access to its functionality

At this point, all kernel components should be fully initialized, and ready to start and manage multiple user-mode processes.

Conclusions

During the making of this article, some adjustments were performed to the various pages of the kernel components. It was mostly about adjusting for the precise order in which components must be initialized. However, one thing also became clear : RPC is not a very good channel for communication between kernel components, and in particular for in-kernel interrupt handling. For this reason, I introduced a version of InterruptHandler::connect_interrupt() which allows connecting an interrupt to a synchronous, fast but deadly entry point inside of the kernel, along with the associated InterruptHandler::disconnect_interrupt() buddy. This will be it for now.

One thought on “On in-kernel dependencies

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s