#CPU Sharing question.
10 messages in this thread
Hello folks, here's a techie question for you…
I'm working on building a .library that will allow multiple processes to
access a RAM resident database. Any one of these process may add, delete,
or search for a record. Because of potential conflicts between these
activities, I will be spawning off a daemon task that will handle the
deletions, additions, and database restructuring on its own, in a FIFO
fasion.
My question is: Given that the other processes and tasks will be forced to
wait while the daemon does its work (ie. if task A wants to delete a record
from the database, it will send a message to the daemon and wait for the
reply before continuing.), should I worry about the daemon getting its fair
share of CPU time? Or, should I play games with its priority? Or what is
the proper way to handle this?
I'd set the daemon at a priority of +5 over the other database
program(s). My reasoning is that you want an updates, etc. to complete as
fast as possible. Otherwise you'll leave your self open for a slowdown and
a good possibility of losing data integrity.
Figure user A wants to update record 1234 and the message gets
passed to your daemon. User B wants to read record 1234. The daemon
starts to do the update, but it's time slice ends before it's done. Since
the reader program (user B) is running at the same priority…it starts
it's read operation on the partially updatted data.
Another way to handle that, whatever the priority, is to have the
daemon, as it's first task, lock the record via a flag. Then user B, when
attempting to read the record, would "see" that flag and wait until the
flag was cleared. But even doing it that way, you'd want the update
operation to complete as fast as possible so that user B didn't have to
wait too long.
In fact, what I'm doing is setting up an internal queue mechanism, using an
EXEC list (or something similar of my own). Essentially, search (and
read), add, delete and restructure (rebuild the index) operations will be
queued. Add and delete operations will have the highest priority, followed
by search and then restructure (which simply makes the index more
efficient).
The queueing will allow several searches to occur at once. When another
operation is placed into the queue, however, it will wait until all active
searches are complete. Then the system will execute this other request
(whatever it is). So, on a given database (I may have several), there may
be several searches going on, or only one of delete, add, restructure.
That should take care of the contention that you spoke of.
In fact, I'm beginning to rethink the entire idea of having a daemon to do
some of this work. Having one task handle all of the updates may be too
much of a bottleneck.
Chris -)—–
Chris,
Having one process do all the work, means you're back to a single
user concept…which I presume you want to get away from by having separate
tasks. If user 1 is doing a long search and user 2 wants to update a
single record and user 3 wants to see a certain record…only user 1 is
happy, because his request is being worked on. User 2 walks away from the
terminal waiting for his request to occur and user 3 is fuming about
nothing happening at all.
There's no reason a read can't be done even if there is a pending
update queued. As long as you insure data integrity via record locking
that is.
Don
Yes, you are correct.
My indexing system is the good old AVL tree. As many searches as you like
can be done at the same time, and you can even add index entries (one at a
time) while searching is going on. (Because the addition of the index
entry always occurs at a leaf node, and the final link up is a single
instruction.) Deletions are more complex, because you may have to move
subtrees around. Restructuring is the worst, because you have to climb back
up the tree and rebalance at each node until you create a properly balanced
tree (which could involve adjusting things up the entire height of the
tree).
So, the situation is this: I've got to queue up the searches, adds,
deletes, and restructures for each database in memory. When a search is
running, I can continue to allow other searches on the same database to
start. When I get a delete or rebuild in the queue, I have to let the
searches finish before I can start the delete or rebuild. A single add may
be run while searches are still going. Once that add is finished, another
add may start.
So: How to I put the tasks that are waiting (while their delete is in the
queue, for example) into a proper wait state, and how do I wake them up. I
guess that this is an EXEC question. I want to use a mechanism that is
private and that does not have any serious limits on the number of tasks
that it is juggling. Low overhead would be nice too.
Chris,
One of two mechanisms…
semaphores or messages. Have a master process, the 'brain' if you
will. This would be the traffic cop of the system, all database access
must ask permission of the master program (via a message or semaphore) and
wait for a reply to continue before it goes on. When it's done, it tells
the master program it's done.
Thus, the master can allow multiple searches to run at once, or a
single add plus a search….but won't allow and updates, resturctures or
deletes to occur until all searches are finished (or anything else that
would conflict).
When a program has made a request for an action, and until it
receives permission to proceed…it simply waits for the master to tell it
to proceed. WaitPort() would be appropriate for this if you were using
messages. The process calling WaitPort() will sleep until a message is
received.
The master can be a very simple program. It only needs a local
stack where it stores what operation(s) are in progress and a 2nd stack of
what requests have been made. And then of course, it needs the IPC
facilities.
Don
Ok, sounds good. I'm working on learning about semephores. I like the
idea of semiphores better than message ports, because there is an upper
limit to the number of message ports a task may have. I don't want my code
to interfere with the code that another programmer may want to build on top
(I'm creating a library), so I don't want to use any resource that someone
else may need later.
A bit quirky of me, I know, but that's the way I iz.
Chris -)—–
Thanks!
Chris,
Ok…if memory serves me right, there's only 8 user bits in a
semaphore available….but if you used 5 of those bits for process
identification and the other 3 bits (if 8 is correct) for the nature of the
request, that'd allow you to have 32 processes and 8 types of
requests/replies for communication.
I could be way off on the number of bits available….it's been a
while since I looked at semaphores.
Don
Don,
I'm looking at Mortimore's "Amiga Programmers Handbook". It covers
AmigaDOS 1.2 &c., so it's a bit out of date. However, according to what it
says here, there are no signal bits in the SignalSemaphore structure.
There is a node substructure, a nestcount, a MinList queue of tasks waiting
to gain control of the semaphore, a linked list of Semaphore Request
structures, a pointer to the task that owns the semaphore, and a count of
the number of tasks waiting in the queue.
If anything has been added to this strucure that would allow shared access,
I would be thrilled! I'll have to look into my more up-to-date
documentation.
Chris -)—–
Chris,
No, nothing else has been added to it, but it's use has been
explained much better in the latest ROM Kernel manual from Commodore
(published by Addison Wesley. You'd need the libraries and devices manual.
Also look at the section on signals. (BTW…it's 16 bits in a signal that
are available, not in a semaphore…my mistake there)
Don