MessageQueue implementation using only pager?

[carbonBased]

Hello,

I've written what I call "local" implementations for fundamental sync utilities; mutex, semaphore and message queue's (they'll work fine for threads in the same address space, but not for tasks in separate address spaces).

For separate address space fundamentals, I'd like to make them use only full pages for their memory allocations (that way they're easy to map into separate address spaces using the pager). I figure I'll use an ID for each of these, which will actually be a physical memory pointer, and tasks that wish to use these will then map them into their own shared memory address space.

My problem is the message queue. Semaphore and Mutex only need to hold one expanding list -- the list of waiting tasks. This is fairly easy to implement inside a page. Message Queue's need to hold an expanding list of waiting tasks and pending messages. This doesn't fit will inside one page. I could use separate pages for the task list and the messages, but then I'd be wasting a portion of a page.

How are you guys implementing separate address space message queues?

Thanks,
Jeff

[carbonBased]

I suppose an alternative question is -- do you allow unlimited/expanding message queues, or does your OS limit the size of a message queue?

By limiting the size of a message queue, I then only have one expanding list - the waiting tasks, and things are more simplified... but limited.

What are your thoughts on this approach?

--Jeff

[pcmattman]

Message queues (which I have only yet designed, not implemented) in my OS are based around a linked list, FILO style. Whenever a new message comes in, it's popped off the list on a GetMessage() call. Each process has their own message queue, and data is read via a syscall.

I've seen implementations where the size is limited to 1 message, and to send a message to another process can be an extremely long process if the other process has not yet read their message (you don't write over another message).

[Brendan]

Hi,

How are you guys implementing separate address space message queues?

For each message queue I have a linked list of N pages in kernel space (where N may be zero if there's no messages in the queue). Each page contains 1 or more messages. Each message's data in the queue may be raw bytes, or page table entries, or page directory entries, so that the message data is always less than 2 KB regardless of how large the message itself is.


Cheers,

Brendan

[carbonBased]

Message queues (which I have only yet designed, not implemented) in my OS are based around a linked list, FILO style. Whenever a new message comes in, it's popped off the list on a GetMessage() call. Each process has their own message queue, and data is read via a syscall.

Soundn't a message queue really be FIFO? FILO sounds more like a stack then a queue to me.

My single-address space message queue's use a linked list but, because of this, they rely on a byte allocator which I wish to remove from my micro kernel in favor of working only with the pager.

I've seen implementations where the size is limited to 1 message, and to send a message to another process can be an extremely long process if the other process has not yet read their message (you don't write over another message).

Indeed, I definitely wouldn't limit the size to 1. The intent would be to allow the develop to specify a limit so that the creation routine could automatically map in the appropriate number of pages to handle it.

--Jeff

[carbonBased]

For each message queue I have a linked list of N pages in kernel space (where N may be zero if there's no messages in the queue). Each page contains 1 or more messages. Each message's data in the queue may be raw bytes, or page table entries, or page directory entries, so that the message data is always less than 2 KB regardless of how large the message itself is.

I see. And a similar linked list of pages of tasks waiting on the message queue?

--Jeff

[pcmattman]

Soundn't a message queue really be FIFO? FILO sounds more like a stack then a queue to me.

My single-address space message queue's use a linked list but, because of this, they rely on a byte allocator which I wish to remove from my micro kernel in favor of working only with the pager.

I should probably use FIFO. As I said, not implemented yet, haven't seen the errors in it yet.

[Brendan]

Hi,

For each message queue I have a linked list of N pages in kernel space (where N may be zero if there's no messages in the queue). Each page contains 1 or more messages. Each message's data in the queue may be raw bytes, or page table entries, or page directory entries, so that the message data is always less than 2 KB regardless of how large the message itself is.

I see. And a similar linked list of pages of tasks waiting on the message queue?

Not for my OS. Every thread has exactly one message queue (where "messagePortID" is the same as "threadID"), which means only one thread can be waiting for a message to be received at a message queue. Sending a message never involves any blocking.

The end result is that I don't need a list of waiting threads. All I use is a single "waiting for message" flag for each thread.


Cheers,

Brendan