OSDev.org

It seems to me that an awful lot of CPU cycles are wasted with context switching in the name of the illusion of concurrency.

I don't have everything clear in my mind about what I am about to suggest but basically it goes as follows. The OS should avoid context switching by having one single process run with a global event loop. New programs could be added to the system by integrating into this global event loop.

My motivation comes from observing the performance gains of Nginx over Apache. Nginx uses an event loop with epoll rather than multiple threads of the Apache model to service HTTP requests. If this can work at the server level why not system wide?

I think your premise that the purpose of multiple processes is to provide (the illusion of) concurrency is false. To my mind the main purpose is to avoid wasting CPU cycles.

jamesread wrote:If this can work at the server level why not system wide?

Apache spawns a process/thread to handle each incoming connection. That has high overhead. But there is no universal system wide analogue of "handling a connection", in the sense that programs on your average desktop PC generally do not try to handle 100k of concurrent I/O operations in a uniform fashion (across different programs).

jamesread wrote:It seems to me that an awful lot of CPU cycles are wasted with context switching in the name of the illusion of concurrency.

I don't have everything clear in my mind about what I am about to suggest but basically it goes as follows. The OS should avoid context switching by having one single process run with a global event loop. New programs could be added to the system by integrating into this global event loop.

My motivation comes from observing the performance gains of Nginx over Apache. Nginx uses an event loop with epoll rather than multiple threads of the Apache model to service HTTP requests. If this can work at the server level why not system wide?

I think what you are describing is a special case of Co-operative multitasking... such a paradigm has many disadvantages over the preemptive model which almost all operating systems use today.

-edit- Your suggested approach is a security nightmare, if security isn’t a primary concern, you should look at my OS, where a context switch is no more expensive than a function call, as I don’t use virtual memory. A context switch is little more than a stack swap!

jamesread wrote:It seems to me that an awful lot of CPU cycles are wasted with context switching in the name of the illusion of concurrency.

Have you measured it?

jamesread wrote: I don't have everything clear in my mind about what I am about to suggest but basically it goes as follows. The OS should avoid context switching by having one single process run with a global event loop. New programs could be added to the system by integrating into this global event loop.

We've tried this before.

The results weren't pretty.

You need to put the context switch overhead into context. CPU intensive applications won't context switch much, so the relative overhead is low.

I/O intensive applications, especially those waiting on human input, spend most of their time asleep, making context switches neither here nor there.

However, for specialized and/or embedded systems, where trust and security are not as much of a problem, this is a very reasonable approach to take.

Of particularly low overhead are systems like protothreads, which provides thread like services on a single stack and tiny overhead.

thewrongchristian wrote:

jamesread wrote: I don't have everything clear in my mind about what I am about to suggest but basically it goes as follows. The OS should avoid context switching by having one single process run with a global event loop. New programs could be added to the system by integrating into this global event loop.

We've tried this before.

The results weren't pretty.

It's been tried in a number of systems, mostly older ones such as the aforementioned Windows 1.0. The last serious instance of a polling cooperative multitasking system I am aware of was Oberon, which relied on the compiler for the language of the same name to ensure that processes released the CPU periodically.

Note that the system required a compliant compiler designed specifically to insert yields into the code at periodic intervals, otherwise a program could simply never yield and potentially lock the system up, or at the least lock out any other processes (including the kernel itself). This, however, was due to the absence of any interrupts in the OS, and indeed the Ceres workstation it was originally implemented on had no usable interrupts of any sort (though the underlying NS 32000 CPU supported them, the workstation itself didn't have any interrupt controllers).

But even with a clock or timer interrupt to force the system into the scheduler (that is to say, preemption), a single primary system-wide event loop leads to a number of problems. First off, in a modern multi-core system, it means either using only a single core, or else having the separate cores operate entirely separately - which would lock you out of most forms of IPC.

Second, it means that you would in effect be running everything in System mode (or Supervisor mode, or Ring 0, whatever a given CPU designer calls it). Most of your protection mechanisms are thrown out the window when you do this.

Third, it leads to a potential situation similar to the Global Interpreter Lock used in some Python implementations - anything that locks out the interrupts and/or fails to yield to the scheduler for an extended period can lock up the whole system.

jamesread wrote:It seems to me that an awful lot of CPU cycles are wasted with context switching in the name of the illusion of concurrency.

I don't have everything clear in my mind about what I am about to suggest but basically it goes as follows. The OS should avoid context switching by having one single process run with a global event loop. New programs could be added to the system by integrating into this global event loop.

My motivation comes from observing the performance gains of Nginx over Apache. Nginx uses an event loop with epoll rather than multiple threads of the Apache model to service HTTP requests.

The primary purpose of context switching is to provide concurrency (or, on single-core systems, the illusion of concurrency) along with isolation between programs. This is to make sure that if program A barfs, it only barfs on itself, and no puke gets splashed on program B. Keep in mind that the earliest systems that context switched between processes were multi-user systems (and most modern systems are capable of running as multiuser systems even if they typically are used by a single person), and on such a system, you not only have to prevent buggy programs from barfing on each other, but you also have to prevent users from doing nasty things to other users they don't like, or from viewing data they aren't supposed to have access to, or from playing dirty tricks to get more than their share of system resources. If Alice is running a compile job for a program that ships next week, and Bob is playing a game that's running slowly due to Alice's compile job, you don't want Bob to be able to crash Alice's compile job to free up CPU time for his game. On many (but not all) of these early systems, each user's login session ran as a single process in a separate address space, but individual programs run by a given user were integrated into the event loop for the user's login process, rather than spun off as separate processes.

If this can work at the server level why not system wide?

Remember how crashy Windows 3.x and 9x were? That was because Win16 programs were all run in one process with one huge event loop, which also contained a good chunk of Windows itself. So a program that crashed could end up damaging other programs, trashing the event loop, or otherwise damaging Windows itself, with the latter two cases bringing the whole system down. In NT-kernel Windows (all of the professional versions of 32-bit Windows, and all of the home versions from XP on), at the cost of some back-compatibility, the process that contains all of the Win16 applications doesn't contain any part of Windows except the Win16 subsystem itself, so a misbehaving Win16 application can't affect the system as a whole, it just causes the Win16 subsystem to crash (taking down all other Win16 apps with it). 64-bit versions of Windows have ditched that entire subsystem, so Win16 apps can't run at all (though there is a 3rd party solution or two that can run Win16 apps on 64-bit windows).

Schol-R-LEA wrote: It's been tried in a number of systems, mostly older ones such as the aforementioned Windows 1.0.

It actually applies to Win16 applications on any version of Windows that can run them (I believe you can set up NTVDM to run each Win16 app in its own NTVDM instance, but IIRC this isn't the default).

For Windows 3.x (in enhanced mode) and 9x, each concurrent DOS application started from within Windows ran in its own preemptively-multitasked process with its own address space, but the whole stack of DOS code loaded before Windows was mapped in every DOS process and was available for any crashing DOS application to barf on and kill the system. Windows itself (I think except for the parts that needed to be accessible in any process, such as interrupt handlers, the scheduler for DOS processes, and all of the paging/segmentation management code) ran as one of these processes, and ran all Win16 applications in one big cooperatively multitasked event loop in that process.

Win32 processes in Win9x, as far as I've been able to determine, were also each run in their own process, but I'm less certain if they had low DOS memory mapped at the bottom of their address space as with DOS processes, and it seems (though I'm even less certain) that a lot of system services got funneled through the Win16 subsystem, creating a single point of failure if a Win16 application crashed.

In NT kernel Windows, there's no critical system functionality that runs under NTVDM, so it isn't a single point of failure for the system, but, by default, all Win16 applications run in a single NTVDM instance.

I read a book on the design of Windows 95 once. The system would preemptively multitask virtual machines. One virtual machine was the Win32 machine, which in turn would preemptively multitask Win32 thread. The DOS VM used singletasking, while the Win16 VM used cooperative multitasking. The subsystems were independent of each other, so one could go down and others would continue running. Windows 9x's problem was the fact that Win32 apps could trample on the low 1M, they could trample on the shared heap, and they could trample on the kernel. That made for a very unstable system.

nexos wrote:I read a book on the design of Windows 95 once. The system would preemptively multitask virtual machines. One virtual machine was the Win32 machine, which in turn would preemptively multitask Win32 thread. The DOS VM used singletasking, while the Win16 VM used cooperative multitasking. The subsystems were independent of each other, so one could go down and others would continue running. Windows 9x's problem was the fact that Win32 apps could trample on the low 1M, they could trample on the shared heap, and they could trample on the kernel. That made for a very unstable system.

Here's a PDF that has lots of nasty details. Is this the one?

I've just skimmed part of the MM chapter, and it bought me out in a cold sweat.

No, actually it was about driver programming, but the first couple chapters explained the basic architecture.

I don't think that what I have in mind is a cooperative multitasking system. I had to look up what one was but as far as I can see there is still context switching involved in a cooperative multitasking system when a process yields.

What I have in mind is a single process with no context switching. 'Programs' are pieces of code which integrate with this single process and compete for resources via a global event loop. Concurrency is achieved by servicing the 'programs' when it becomes possible as indicated by the global event loop.

bloodline wrote:Your suggested approach is a security nightmare, if security isn’t a primary concern, you should look at my OS, where a context switch is no more expensive than a function call, as I don’t use virtual memory. A context switch is little more than a stack swap!

Your approach is no less of a security nightmare than the OP's.

The only way to get this to work is to write all of userspace in a managed, safe language.

(I don't know if you do this or not; but either way your approach is, from a security perspective, at parity with the OP's.)

jamesread wrote:I don't think that what I have in mind is a cooperative multitasking system. I had to look up what one was but as far as I can see there is still context switching involved in a cooperative multitasking system when a process yields.

What I have in mind is a single process with no context switching. 'Programs' are pieces of code which integrate with this single process and compete for resources via a global event loop. Concurrency is achieved by servicing the 'programs' when it becomes possible as indicated by the global event loop.

It depends what you call a ‘context switch’ (or, perhaps more accurately, what you call a ‘context’). In the classic async paradigm, the only thing that changes when you yield is the stack pointer. Completely aside the fact the fact that swapping out the stack pointer is effectively free, consider this:

When you call a function (or return from one), the stack pointer changes. Has the context of the program been changed meaningfully following a function call? Arguably, yes. Do you intend to disallow function calls? (Probably not...)

Maybe function calls are too mundane. How about exceptions? They do funky things to the stack. (Ditto setjmp/longjmp which, incidentally, are sufficiently powerful to implement both exceptions and coroutines.) Same with primitives like call/cc.

------------------------------------------------------------------

The point is this: the meaning of the word ‘context switch’ is not precisely defined, but contextual. The question is what meaningful result do you want to get from your multitasking-free OS? You alluded to performance in your top-level post; coroutines perform wonderfully.

(Will the CPU be able to speculate stack accesses slightly better with an explicit event loop than with coroutines? Maybe. Will this difference be measurable? Probably not, outside maybe from some pathological cases. Compared with CPU-level protection changes, coroutines aren't meaningfully slower than an explicit event loop.)

moonchild wrote:

bloodline wrote:Your suggested approach is a security nightmare, if security isn’t a primary concern, you should look at my OS, where a context switch is no more expensive than a function call, as I don’t use virtual memory. A context switch is little more than a stack swap!

Your approach is no less of a security nightmare than the OP's.

Yes, I did clearly state that the OP should only look at what I’m doing if security is NOT a concern.

I what is clearly a concern for the OP is the CPU cycle cost of a context switch, which is a primary consideration for my design... thus the OP would see that one doesn’t need to lose the benefits of a preemptive multitasking system, just because they don’t like the cost of context switching.

The only way to get this to work is to write all of userspace in a managed, safe language.

Which is one approach I have discussed on this forum... I’m still exploring how security might be implanting a low overhead way.

(I don't know if you do this or not; but either way your approach is, from a security perspective, at parity with the OP's.)

Right now the most secure thing about my OS is that no one uses it... or is ever likely to