What decides which application will get the next turn for cycles within a CPU?

[Smartazz]

When you are multitasking with a single core chip and the different applications are taking turns on the CPU executing instructions, what decides which programs get the next turn on the core? Thanks in advance.

 

[PhatoseAlpha]

The OS kernel handles scheduling decisions. The details are dependent on the kernel implementation.

 

[Smartazz]

Originally posted by: PhatoseAlpha
The OS kernel handles scheduling decisions. The details are dependent on the kernel implementation.

Different operating systems have more efficient kernel systems right? So would that mean that Vista might be better than XP at multitasking if it were more efficient in that respect?

 

[Cogman]

Originally posted by: Smartazz

Originally posted by: PhatoseAlpha
The OS kernel handles scheduling decisions. The details are dependent on the kernel implementation.

Different operating systems have more efficient kernel systems right? So would that mean that Vista might be better than XP at multitasking if it were more efficient in that respect?

yes.

Don't know what else to say, if all tasks are equal in priority, windows xp will favor the window that has focus. I don't know how it is with linux, but that is how it is with win xp

 

[CTho9305]

To give a little more detail for the original question, you might wonder how the OS kernel can do scheduling while a program is running. It actually doesn't - a hardware timer ticks every so often (5ms or so), and causes the CPU to jump back into kernel code from whatever application it's currently running. The kernel can then decide to either continue running the current application, or pick another one to run during the next timeslice. The algorithms used here will affect overall throughput and how responsive the system feels.

Don't know what else to say, if all tasks are equal in priority, windows xp will favor the window that has focus.

That behavior is actually configurable. System Properties->Advanced->Performance->Advanced, under Processor scheduling.

 

[bobsmith1492]

As of Win2000/XP it was changed over so that the OS has full preemptive context switching. Before, the programs had to yield processor control to the kernel periodically; that meant if one thread locked up, it could grab control, go into a loop, and lock the processor for good.

Performance depends on how many timeslices are allocated to whichever process (this is controlled by the priority settings in XP at least) and the amount of overhead required for context switching (swapping data in/out of the CPU registers to allow the CPU to run a different thread). From what I hear overhead for switching was something like 10-20% of CPU time for Windows XP. I don't know where those numbers come from, but that's what I heard.

 

[Smartazz]

If you go into Windows Task Manager and show kernel times, is that how much of the CPU scheduling is being used strictly for allocating the time slices?

 

[CTho9305]

Originally posted by: bobsmith1492
As of Win2000/XP it was changed over so that the OS has full preemptive context switching. Before, the programs had to yield processor control to the kernel periodically; that meant if one thread locked up, it could grab control, go into a loop, and lock the processor for good.

I'm pretty sure that's not true. Windows 95 and newer used preemptive multitasking; the only "major" OS in the same time-frame that used cooperative multitasking was Mac OS (the first version of Mac OS that used preemptive multitasking was OS X).

From what I hear overhead for switching was something like 10-20% of CPU time for Windows XP. I don't know where those numbers come from, but that's what I heard.

Not a chance. Write a program that counts to, say, 2 billion 10 times and time it. You'll find that you get very very close to the theoretical speed of your CPU. IIRC, context switches take a handful of microseconds, while timeslices are multiple milliseconds.

 

[Matthias99]

Originally posted by: CTho9305

Originally posted by: bobsmith1492
As of Win2000/XP it was changed over so that the OS has full preemptive context switching. Before, the programs had to yield processor control to the kernel periodically; that meant if one thread locked up, it could grab control, go into a loop, and lock the processor for good.

I'm pretty sure that's not true. Windows 95 and newer used preemptive multitasking; the only "major" OS in the same time-frame that used cooperative multitasking was Mac OS (the first version of Mac OS that used preemptive multitasking was OS X).

Win95 and up have preemptive multitasking -- but not if you set your applications/threads to realtime priority and they then lock up. But that's an explicit feature for getting more control over the scheduler. Normal programs can be preempted at almost any time.

From what I hear overhead for switching was something like 10-20% of CPU time for Windows XP. I don't know where those numbers come from, but that's what I heard.

Not a chance. Write a program that counts to, say, 2 billion 10 times and time it. You'll find that you get very very close to the theoretical speed of your CPU. IIRC, context switches take a handful of microseconds, while timeslices are multiple milliseconds.

OTOH, if you wrote a program that could spawn any number of threads to do a task, and you spawn way more threads than you have processors, it will hurt overall. The context switching overhead starts to become significant. The switching itself isn't that bad -- but it generally causes tons of L1/L2 cache misses, which starts to chew into performance.

 

[CTho9305]

You can try http://ctho.ath.cx/tmp/counter/Debug/counter.exe if you want. I don't know if it would produce the right answer on Intel CPUs (I think it should). In theory, it should take 20 billion cycles (so, 10 seconds on a 2GHz chip). I get 1.6 GHz when running it normally, and 1.7GHz when setting the priority to real time (my browser, acrobat, winamp, and a couple other things use a few percent of the CPU time in the "normal" priority run). This puts the overhead at ~2% given the 1724MHz reported by WCPUID (and who knows what other stuff is happening besides the scheduler, e.g. hardware interrupts).

If you don't trust my binaries, you can build and run http://ctho.ath.cx/tmp/counter/counter.cpp.

(edit: Divide the result by 2 for Core 2 CPUs - their "loop buffer" eliminates the branch-taken bubble associated with the jne, allowing a loop iteration every cycle instead of every other cycle)

Win95 and up have preemptive multitasking -- but not if you set your applications/threads to realtime priority and they then lock up.

I would still consider it preemptive. Set two processes to realtime, and observe them both running.

 

[Smartazz]

Originally posted by: CTho9305
You can try http://ctho.ath.cx/tmp/counter/Debug/counter.exe if you want. I don't know if it would produce the right answer on Intel CPUs (I think it should). In theory, it should take 20 billion cycles (so, 10 seconds on a 2GHz chip). I get 1.6 GHz when running it normally, and 1.7GHz when setting the priority to real time (my browser, acrobat, winamp, and a couple other things use a few percent of the CPU time in the "normal" priority run). This puts the overhead at ~2% given the 1724MHz reported by WCPUID (and who knows what other stuff is happening besides the scheduler, e.g. hardware interrupts).

If you don't trust my binaries, you can build and run http://ctho.ath.cx/tmp/counter/counter.cpp.

Win95 and up have preemptive multitasking -- but not if you set your applications/threads to realtime priority and they then lock up.

I would still consider it preemptive. Set two processes to realtime, and observe them both running.

Thanks for the program. I got 2.33GHZ on a 2.4GHZ chip. So if I get this straight, .07GHZ goes to overhead in the operating system?

 

[Matthias99]

Originally posted by: CTho9305

Win95 and up have preemptive multitasking -- but not if you set your applications/threads to realtime priority and they then lock up.

I would still consider it preemptive. Set two processes to realtime, and observe them both running.

I actually thought from the documentation that it wouldn't preempt/switch away from a REALTIME priority thread (I thought you had to explicitly yield() or do a blocking operation). It will definitely switch back and forth between multiple REALTIME processes/threads as long as they occasionally give up control.

But it's been a while since I was working with that stuff, and in the project I was working on I only had a single REALTIME process/thread.

 

[CTho9305]

I asked stash about this. I'd be interested in hearing whether it interrupts realtime processes or not.

 

[bsobel]

Originally posted by: CTho9305
I asked stash about this. I'd be interested in hearing whether it interrupts realtime processes or not.

Absolutely, and being the highest priority thread, it will immediately get rescheduled and execute again.

 

[bsobel]

Originally posted by: Smartazz

Originally posted by: PhatoseAlpha
The OS kernel handles scheduling decisions. The details are dependent on the kernel implementation.

Different operating systems have more efficient kernel systems right? So would that mean that Vista might be better than XP at multitasking if it were more efficient in that respect?

That is correct, Vista does include some scheduler changes.

 

[bsobel]

Originally posted by: Smartazz
If you go into Windows Task Manager and show kernel times, is that how much of the CPU scheduling is being used strictly for allocating the time slices?

No, that includes all times spent in kernel (device drivers, io, etc)

 

[stash]

Originally posted by: bsobel

Originally posted by: CTho9305
I asked stash about this. I'd be interested in hearing whether it interrupts realtime processes or not.

Absolutely, and being the highest priority thread, it will immediately get rescheduled and execute again.

Yeah, if I'm reading my copy of Windows Internals correctly, that is correct.

 

[Smartazz]

Originally posted by: bsobel

Originally posted by: Smartazz
If you go into Windows Task Manager and show kernel times, is that how much of the CPU scheduling is being used strictly for allocating the time slices?

No, that includes all times spent in kernel (device drivers, io, etc)

Oh, ok thanks.

 

[Nathelion]

As to saying that one OS is "better" at managing time allocation than another... it depends entirely what you use it for. Batch-mode systems obviously don't need to do any context switching at all, systems with few resource-intensive threads would benefit from different algorithms than systems with many smaller threads, etc... That being said, I sure hope Vista is better than XP for your average desktop user, it'd be pretty sad otherwise.


Quote:
"OTOH, if you wrote a program that could spawn any number of threads to do a task, and you spawn way more threads than you have processors, it will hurt overall. The context switching overhead starts to become significant. The switching itself isn't that bad -- but it generally causes tons of L1/L2 cache misses, which starts to chew into performance. "

I'm curious about that. I thought the caches were saved to memory and switched out every time the processor manager switched threads. Are you sure it doesn't?

 

[bsobel]

I'm curious about that. I thought the caches were saved to memory and switched out every time the processor manager switched threads. Are you sure it doesn't?

I think your thinking of state and regsiters. L1 and L2 are small shared resources, and 'saving them to memory' doesn't exist, they are a cache of memory. If direct memory access was fast enough, they wouldnt need to exist.