OSDev.org

If a service uses multiple threads to complete a request, then the scheduler sees seperate threads and schedules each independantly. If a services uses one thread per CPU, then (hopefully) this results in all CPUs doing the request, but the scheduler still sees seperate batch processing threads.

Colonel Kernel wrote:IMO, efficient multitasking of multiple CPU-intensive threads on a single CPU is a pointless exercise.

Colonel Kernel wrote:Stop thinking about threads and start thinking about systems. Is the minor gains you're going to see from this really worth the effort or added complexity? Is the world clamouring for this feature? I just don't see it. Sometimes the right answer is: Break that fence into 2, 4, or 8 pieces and have a painter on each one. The world will be drowning in painters before you know it -- might as well figure out how to use them all (or more to the point, encourage application developers to do so).

Colonel Kernel wrote:If my answers always seem like this, it's because I know you're trying to make BCOS a commercial OS. If this were just a hobby, I'd keep my mouth shut, but when it comes to commercial software projects, I can't help but point out instances of requirements scope creep.

frank wrote:I have just one simple question dealing with the painter analogy. What if the one painter has to prime the fences first and then has to wait for the primer to dry. Does the painter A - wait for the paint to dry and then continue or B - go onto the next fence while waiting for the paint to dry. If he choose A then there would be a lot of wasted time waiting for the paint to dry. Just a thought.

Combuster wrote:I have some more brain teasers regarding practicality:

Consider an IO-bound batch program (real world example: computing the MD5 of a dvd image for some p2p application), and an CPU-bound program (the user is running bittorrent in the background while playing with blender)
now the download completes and the hashing starts, and shortly after the user wants to render his model. One would get the following:
the scheduler will hop from task to task when a disk track completes, causing lots of scheduling overhead and TLB flushes as the raytracer is scheduled out each time disk data is ready. A more stock scheduler would give the raytracer a better share of cpu time, then return to the MD5 which has by that time a sensible amount of disk data to work on.

Combuster wrote:The other brain teaser is about ported GNU tools: they are not scheduler-aware and will always run in parallel mode, giving cause to just that which you are trying to avoid. (which was also the reason why I said i wasn't satisfied by your explanation)

Combuster wrote:The last one (more philosophically), is wether or not there are always corner cases to find that ruin the advantages of an particular scheduling algorithm.

Combuster wrote:Dilemmas like these are a reason why I have pluggable schedulers on the wish list for my own kernel...

brendan wrote:Policy 0 - Co-operative scheduling for device drivers (e.g. IRQ handlers), where the highest priority task in this policy gets all CPU time (but where the scheduler monitors time used and terminates the thread if it uses more than N ms).

brendan wrote:Policy 1a - High priority variable time slice for normal high priority threads, where all threads within this policy get N ms (where N depends on the threads priority) and threads take turns.
Policy 1b - High priority batch processing, where the oldest thread that can run is run and gets all CPU time (but where the scheduler monitors time used and terminates a thread if it uses a total of more than N ms).

brendan wrote:Policy 2a - Normal priority variable time slice for normal threads, where all threads within this policy get N ms (where N depends on the threads priority) and threads take turns.
Policy 2b - Normal priority batch processing, where the oldest thread that can run is run and gets all CPU time (but where the scheduler monitors time used and terminates a thread if it uses a total of more than N ms).

brendan wrote:Policy 3a - Low priority variable time slice, where all threads within this policy get N ms (where N depends on the threads priority) and threads take turns.
Policy 3b - Low priority batch processing, where the oldest thread that can run is run and gets all CPU time (and the scheduler doesn't monitor time used).

os64dev wrote:

brendan wrote:Policy 0 - Co-operative scheduling for device drivers (e.g. IRQ handlers), where the highest priority task in this policy gets all CPU time (but where the scheduler monitors time used and terminates the thread if it uses more than N ms).

Co-operative scheduling with a scheduler monitoring and interrupting. That's plain preemption with a yield added to the drivers. Which imho would happen automatically if they block on semaphores.

os64dev wrote:

brendan wrote:Policy 3a - Low priority variable time slice, where all threads within this policy get N ms (where N depends on the threads priority) and threads take turns.
Policy 3b - Low priority batch processing, where the oldest thread that can run is run and gets all CPU time (and the scheduler doesn't monitor time used).

3b actually makes sense because batch processing is in general low priority. Think at batches running over night. I also think a book i have read mentions that batch processing is executed in idle time.

Brendan wrote:Policy 1b and Policy 2B make more sense once you understand that "terminate" isn't the same as "preempt".

mystran wrote:As far as I can see, modern hardware is fast enough

mystran wrote:Brendan, what are you actually trying to do? I mean, what is the fundamental goal of this all?

int find_sum(int max) {
    int result = 0;

    for(i = 0; i < max; i++) {
        result += i;
    }
    return result;
}

int find_sum(int max) {
    int workers;
    int range;
    int i;
    threadID *threadList;
    int result = 0;

    workers = get_number_of_CPUs() - 1;

    if( max / 4 < workers) {
        workers = max / 4;
    }

    if(workers == 0) {
        for(i = 0; i < max; i++) {
            result += i;
        }
        return result;
    }

    range = max/(workers + 1);
    threadList = malloc( sizeof(threadID) * workers);

    for(i = 0; i < workers; i++) {
        threadList[i] = spawnThread( &workerThread );
    }

    for(i = 0; i < workers; i++) {
        sendMessage(threadList[i], SUM, i * range, (i + 1) * range);
    }

    for(i = workers * range; i < max; i++) {
        result += i;
    }

    while(workers > 0) {
        getMessage();
        if(message.type == WORKER_RESULT) {
            result += message.data1;
        }
    }

    return result;
}


void workerThread(void) {
    threadID client;
    int start = 0;
    int end = 0;
    int i;
    int result = 0;

    while(end = 0) {
        getMessage();
        if(message.type == SUM) {
            client = message.senderID;
            start = message.data1;
            end = message.data2;
        }
    }

    for(i = start; i < end; i++) {
        result += i;
    }

    sendMessage(client, result);
    terminateThread();
}

os64dev wrote:

Brendan wrote:Policy 1b and Policy 2B make more sense once you understand that "terminate" isn't the same as "preempt".

Ok, i thought that you would put the batch back into the batch queue after the time-slice is finished but it seems that the time you give to the batch is actually its life time. So after that time the batch dies whether it finished its work or not. How do you handle the early death situation then? Because the batch has to be submitted again i guess.

jnc100 wrote:[Therefore, (just a thought off the top of my head) if your system allows you to relocate programs at will, would relocating a batch job to a virtual area not used by, e.g. the rapid-response user interface, prevent the need to invalidate everything, e.g. by setting the pages to global (even though they're not)?

edit: or would that just bypass page protection? I assume it would unless you can guarantee that the processes won't try to read each others address space.

Brendan wrote:Also, CPUs are designed to hide the cost of TLB misses (part of being "out of order"), and AFAIK a TLB lookup may be done using data left in the L1 or L2 caches (and might not result in a full read from the memory chips themselves).