some VmScheduler ideas.. answer if you have a bit time

Project:JNode Core
Component:Code
Category:support request
Priority:minor
Assigned:Unassigned
Status:closed
Description
final void registerThread(VmThread thread) {
    if (Vm.isWritingImage()) {
        allThreadsQueue.add(thread, "Vm");
    } else {
        allThreadsLock.lock();
        try {
            allThreadsQueue.add(thread, "Vm");
        } finally {
            allThreadsLock.unlock();
        }
    }
}

CG: here potential problem, here it is:
at first moment Vm.isWritingImage() is true.. we goes to next.. after few time Vm.isWritingImage() is false, but we already in first case. This check is not guranteed and we can get a two threads working with allThreadsQueue.

The second moment is you are using this template for lock/unlock:

try {
    lock();
....
} finally {
    unlock();
}

CG: here also potential problem if failure happens in lock() method (exception, error, eg) and lock was not acquired, we goes to finally and tries to free lock that was not acquired. It can produce problems and corrupt lock.

final VmThread popFirstReadyThread() {
    try {
        // Get access to queues
        queueLock.lock();
	
        final VmThread newThread = readyQueue.first(VmMagic.currentProcessor());
        if (newThread != null) {
            readyQueue.remove(newThread);
	    return newThread;
        }
        return null;
    } finally {
        // Release access to queues
        queueLock.unlock();
    }
}

CG: it's seems as low-performance threads wakeup way. My point is scheduler should follow another way to detect first ready thread. We should not check queue. We should have a counter to top item. At every tick we should decrease it, ant if counter <= 0 we can try to take a first from queue. Also, counter should be implemeted as atomic, because decrement is not thread-safe operation.

CG: what about load balancing?

CG: is one scheduler for one cpu or one for many cpu's? Is one sleep queue for all cpu's or one queue for each cpu? Where is threads, that waits for a signal/condition? Why allThreadsQueue is shared between all cpu's? It's looks like locks that in queue is stops all cpu's.

#1

Vm.isWritingImage() is only true during bootimage creation (i.e. the build time) whereas it is false only during runtime. Also as the bootimage builder is single threaded you don't get a problem here.
Regarding the lock()/unlock() operations themself, if you have a look at their implementation you'll see that they're proper Spinlocks with atomic operations. So you will spin until you really got the lock (without any allocations or something like that), so you also can not get a problem with unlock.

Regarding SMP, the current scheduler is written with single core in mind. There is a highly outdated branch with a new scheduler for SMP but it was never finished.

The counter you're speaking of seems to be hard to implement efficiently at a first look as you'd need to update it for _each_ thread if I understand you correctly. I think no one is seriously working on the scheduler so you could try your idea if it increases the performance.

#2

>>> Vm.isWritingImage() is only true during bootimage creation (i.e. the build time) whereas it is false only during runtime. Also as the bootimage builder is single threaded you don't get a problem here.
If bootimage creator thread is single in system, what's for scheduler in this time? What to schedule? creator-idle thread?

atomic integer may be a simple int guarged by lock, but it should work faster than queue checking and timestamp comparation. Also, possible to use cpu instruction CAS and some other atomic instructions. I know that it present on x86 and sparc. I guess it should be on ppc.

#3

If bootimage creator thread is single in system, what's for scheduler in this time? What to schedule? creator-idle thread?

It doesn't really matter what (if anything) is being "scheduled" at this point. The boot image builder is executing in the Sun JVM on the development platform. The isWritingImage "hacks" in VmScheduler are simply there to make the JNode initialisation sequence work when the code is executed in that context. Unless you are trying to figure out how the boot image is built, you really don't need to know what is going on.

atomic integer may be a simple int guarged by lock, but it should work faster than queue checking and timestamp comparation. Also, possible to use cpu instruction CAS and some other atomic instructions. I know that it present on x86 and sparc. I guess it should be on ppc.

You may well be right, however ... many really smart people have spent many man-years trying to figure out the best way to implement schedulers and locks. The answer is that there is no simple answer.

If you feel like investing time in trying to make JNode's scheduler and locks better, you are welcome to try. However, I think this work is premature since:

  1. JNode multi-processor support is not working yet,
  2. there are no "typical" multi-threaded workloads for JNode yet,
  3. there are no real evidence yet to suggest that this is a significant issue for JNode, and
  4. there is no testing framework for JNode that would allow us to measure overall system performance and performance improvements.

Without all of the above, any attempts to optimize the JNode scheduler / locks will based on pure supposition. You won't know what really needs to be optimized, or whether any supposed optimizations have the desired effect.

#4

Yes, it's right.. but we really have experience of Linux and FreeBSD. I think we should at least see into Linux and FreeBSD kernels. Linux and FreeBSD has a good schedulers with good performance and many ideas used in it is not a clean supposition. They tuned for a many years..

#5

But it is a HUGE leap of faith to suppose that a JNode workload will be like a Linux / Bsd workload. Ditto that the lessons learned with classic OSes with heavy-weight processes are applicable to an OS with light-weight threads and a garbage collector ...

You really need some base workloads and performance measurements before you leap into optimizing.

#6

A little point:

in VmProcessor::reschedule

            // Should we wakeup a sleeping thread?
            VmThread newThread = scheduler.popFirstSleepingThread();

            // Take the first thread from the ready queue
            if (newThread == null) {
                newThread = scheduler.popFirstReadyThread();
            }

This means that low-level thread that wakes-up can preemt hight-priority ready thread.

Also, hight-priority thread can work as long, as possible. Looks like real-time scheduler strategy.

#7

At first, need to know, what for this OS. Desktop and server OS'es needs some different strategies.

Is Jnode should be real-time? Or currently there is no plans?

#8

Also, why we wakes up only one thread? Only one at every tick? i think we need get list and put them to ready queue.

like this:

            // Should we wakeup a sleeping thread?
            VmThread newThread;

            while( (newThread = scheduler.popFirstSleepingThread()) != null ) {
                scheduler.addToReadyQueue( newThread, false, "reschedule.wakeup" );
                newThread.wakeUpByScheduler(); // threadState = RUNNING
            }

            // Take the first thread from the ready queue
            newThread = scheduler.popFirstReadyThread();

#9

#10

JNode is intentended to be a general purpose operating system including server, desktop and certain type of embedded usecases. I belive that the modular architecture and flexibility of JNode should make this possible. For instance it's already possible to configure the desired kind of memory manager at build time and something similar should be possible for the scheduler too in the future. Regarding the case of the hard realtime operating system, this is not a short or midterm goal for JNode but it might be an option sometime in the future.

#11

Why irq dispatch implemented in scheduler? do really needed dispatch threads and send eoi's to hw at every tick/reschedule?
I rewrite irq dispatcher without unsafeSuspend/resume (on wait/notify + helper) and dispatcher is separated thread with hight priority and there is no irq dispatching in reschedule, but .. what dispatch interval really required? Now iterval is set to 1ms and all seems working.. (with mp=no).

#12

The author of the scheduler is inactive nowdays and there is none actively working on the scheduler right now. The main reason for this is that the scheduler appears to be one of the least buggy parts of JNode at least compared to the other parts of the system and we feel that JNode needs more urgent improvements elsewhere. Neverthless if you prefer to work on the shceduler that is perfectly fine. One way to do this could be to spot actual bugs in the shceduler and threading system and try to fix them. A serious performance problem can be considered a bug too and if you can prove it with a testcase which gets better with your fix while no harmful sideffects are detected then you fix has better chances to become part of JNode. Quite some time ago I created several test classes targetted at multithreading, synchronization and the scheduler. You can find them at core/src/test/org/jnode/test/threads/. Currently there are only several basic tests but they can be a starting point for such work. Interesting points to check: test the behaviour of JNode with a large number of concurrent threads, what is the maximum number of threads JNode can handle in theory and in practice. Somtehing like MultiTest can be useful for this. I'm sure you will find problems with this approach pretty soon and then you can try to fix them.

#13

Status:active» fixed

As this was a support request which was answered imho I'm marking this as fixed. If you have further questions please also don't hesitate to join our IRC channel for a realtime talk. For any patches or bug fixes please open a new bug.

#14

... and if you want to continue talking about design issues, a Forum Topic would be more appropriate. For a start, forum topics have better support for "branches" in the conversation.

#15

Status:fixed» closed