OSDev.org

As I've been thinking about this for a few days, I may as well post even though once more I really should be sleeping rather than lurking on forums

What are the best ways to represent things/objects that a process or thread might own, such as message queues?

To be specific, message queues in my kernel are in kernel space and used by applications by passing handles into syscalls. The two ways I've thought of attaching said queue handles to the process info structures is:
a) hash tables. Hash the handle (ie the address in kernel space) to a byte, and use that to index list of lists.
b) A linked list of arrays. For example, ten handle elements, eleventh pointer to the next array.
c) Just a continually realloc'd array of handles.

I think I'm leaning towards (a), but I'm also wondering whether this should all be in the process structure, or should each thread have its own "stuff" (I don't think so).

At the very least, any access to the list of objects (however its represented) would need some sort of mutual exclusion, right? One thread could get switched to and create a new message queue while another thread is in the middle of the kernel send_msg syscall and is checking whether the process has access to that queue.

Is there always a lock on any kind of list of things in process structures (such as file handles) ?

Thanks,
- Mike

(PS: I just coded my scheduler and timer IRQ today. Hopefully in the coming weeks I'll have pics of alternating letters in Bochs to show off )

My kernel's handle manager uses an AVL tree to map handle IDs to the data structure for the handle (IPC endpoint, file, thread, etc), and a bitmap to allocate/free handle IDs. The handle table is per-process - all threads under a process have the same handles. Like you said, mutual exclusion is needed - the handle table is protected by a mutex, so attempts to access or modify the table are mutually exclusive.

AlexExtreme wrote:Like you said, mutual exclusion is needed - the handle table is protected by a mutex, so attempts to access or modify the table are mutually exclusive.

Or use a lock-free concurrent container so the kernel is scaleable.

Option "a" looks like it is performance/space optimized. Is that your intent ?

Questions I would ask for evaluation of structures:

- How often will list be iterated and does it matter if that iteration is slow?
- How much space do I have available for storing such a structure?
- Is there a need to iterate a system wide active resource list?
- Would any structure other than objects be able to enforce thread safety or do I leave thread safety to the programmers?

As for locking of the lists. The only time you need to access the list is to add/remove items from it, unless you have some kind of garbage collection mechanism (which would iterate the list and alter it from time to time). If multiple threads could add or remove items from the list (which I think is likely the case), locking would be needed.

tantrikwizard wrote:

AlexExtreme wrote:Like you said, mutual exclusion is needed - the handle table is protected by a mutex, so attempts to access or modify the table are mutually exclusive.

Or use a lock-free concurrent container so the kernel is scaleable.

YEAH! Everyone should know ABAout that one.