Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm studying CPU's and I know how it reads a program from the memory and execute its instructions. I also understand that an OS separates programs in processes, and then alternate between each one so fast that you think that they're running at the same time, but in fact each program runs alone in the CPU. But, if the OS is also a bunch of code running in the CPU, how can it manage the processes?

I've been thinking and the only explanation I could think is: when the OS loads a program from the external memory to RAM, it adds its own instructions in the middle of the original program instructions, so then the program is executed, the program can call the OS and do some things. I believe there's an instruction that the OS will add to the program, that will allow the CPU to return to the OS code some time. And also, I believe that when the OS loads a program, it checks if there's some prohibted instructions (that would jump to forbidden adresses in the memory) and eliminates then.

Am I thinking rigth? I'm not a CS student, but in fact, a math student. If possible, I would want a good book about this, because I did not find anyone that explains how the OS can manage a process if the OS is also a bunch of code running in the CPU, and it can't run at the same time of the program. The books only tell that the OS can manage things, but now how.

share|improve this question
6  
See: Context switch The OS does a context switch to the app. The app can then request OS services which do a context back to the OS. When the app ends the context switches back to the OS. –  Guy Coder Jul 4 at 6:30
4  
See also "syscall". –  Raphael Jul 4 at 7:16
7  
1  
If the comments and answers do not answer your question to your understanding or satisfaction, then please ask for more info as a comment and explain what you are thinking or where you are lost, or what specifically you need more detail on. –  Guy Coder Jul 4 at 12:15
2  
I think that interrupt, hooking (of an interrupt), hardware timer (with scheduling-handling hook) and paging (partial answer to your remark on forbidden memory) are the main keywords you need. OS needs to cooperate with the processor really closely to run its code only when needed. Thus most of CPU power can be used on actual computation, not its management. –  Palec Jul 5 at 18:50

7 Answers 7

up vote 32 down vote accepted

No. The operating system does not mess around with the program's code injecting new code into it. That would have a number of disadvantages.

  1. It would be time-consuming, as the OS would have to scan through the entire executable making its changes. Normally, part of the executable are only loaded as needed. Also, inserting is expensive as you have to move a load of stuff out of the way.

  2. Because of the undecidability of the halting problem, it's impossible to know where to insert your "Jump back to the OS" instructions. For example, if the code includes something like while (true) {i++;}, you definitely need to insert a hook inside that loop but the condition on the loop (true, here) could be arbitrarily complicated so you can't decide how long it loops for. On the other hand, it would be very inefficient to insert hooks into every loop: for example, jumping back out to the OS during for (i=0; i<3; i++) {j=j+i;} would slow down the process a lot. And, for the same reason, you can't detect short loops to leave them alone.

  3. Because of the undecidability of the halting problem, it's impossible to know if the code injections changed the meaning of the program. For example, suppose you use function pointers in your C program. Injecting new code would move the locations of the functions so, when you called one through the pointer, you'd jump to the wrong place. If the programmer was sick enough to use computed jumps, those would fail, too.

  4. It would play merry hell with any anti-virus system, since it would change virus code, too and muck up all your checksums.

You could get around the halting-problem problem by simulating the code and inserting hooks in any loop that executes more than a certain fixed number of times. However, that would require extremely expensive simulation of the whole program before it was allowed to execute.

Actually, if you wanted to inject code, the compiler would be the natural place to do it. That way, you'd only have to do it once but it still wouldn't work for the second and third reasons given above. (And somebody could write a compiler that didn't play along.)

There are three main ways that the OS regains control from processes.

  1. In co-operative (or non-preemptive) systems, there's a yield function that a process can call to give control back to the OS. Of course, if that's your only mechanism, you're reliant on the processes behaving nicely and a process that doesn't yield will hog the CPU until it terminates.

  2. To avoid that problem, a timer interrupt is used. CPUs allow the OS to register callbacks for all the different types of interrupts that the CPU implements. The OS uses this mechanism to register a callback for a timer interrupt that is fired periodically, which allows it to execute its own code.

  3. Every time a process tries to read from a file or interact with the hardware in any other way, it's asking the OS to do work for it. When the OS is asked to do something by a process, it can decide to put that process on hold and start running a different one. This might sound a bit Machiavellian but it's the right thing to do: disk I/O is slow so you may as well let process B run while process A is waiting for the spinning lumps of metal to move to the right place. Network I/O is even slower. Keyboard I/O is glacial because people are not gigahertz beings.

share|improve this answer
4  
Can you develop more on you last 2. point? I'm curious about this question, and am feeling the explanation is skipped here. It seems to me like the question is "how the OS take back the CPU from process" and your answer tells "The OS handles it". but how? Take the infinite loop in your first example: how does it not freeze the computer? –  BiAiB Jul 4 at 12:40
3  
Some OSs do, most OS at least mess about with the code to do "linking", so the program can be loaded at any address –  Ian Ringrose Jul 4 at 12:59
1  
@BiAiB The key word here is "interrupt". The CPU is not just something that processes a given stream of instructions, it can also be interrupted asynchronously from a separate source - most importantly for us, I/O and clock interrupts. Since only kernel-space code can handle interrupts, Windows can be sure to be able to "steal" work from any running process any time it wants to. The interrupt handlers can execute whatever code they want to, including "store the CPU's registers somewhere and restore them from here (another thread)". Extremely simplified, but that's the context switch. –  Luaan Jul 4 at 14:13
1  
Adding to this answer; the style of multitasking referred to in points 2 and 3 is called "preemptive multitasking", the name refers to the OS's ability to preempt a running process. Cooperative multitasking was used frequently on older operating systems; on Windows at least preemptive multitasking wasn't introduced until Windows 95. I've read of at least one industrial control system in use today that still uses Windows 3.1 solely for its real-time cooperative multitasking behavior. –  Jason C Jul 5 at 6:25
2  
@BiAiB Actually, you're wrong. Desktop CPUs don't run code sequentially and synchronously since about the i486. However, even older CPUs still had asynchronous inputs - interrupts. Imagine a hardware interrupt request (IRQ) just like a pin on the CPU itself - when it gets 1, the CPU stops whatever it's doing, and starts processing the interrupt (which basically means "preserve state and jump to an address in memory"). The interrupt handling itself is not x86 or whatever code, it's literally hardwired. After jumping, it again executes (any) x86 code. Threads are a way higher abstraction. –  Luaan Jul 7 at 11:21

While David Richerby's answer is a good one, it does sort of glaze over how modern operating systems halt existing programs. My answer should be accurate for the x86 or x86_64 architecture, which is the only one commonly in use for desktops and laptops. Other architectures should have similar methods of achieving this.

When the operating system is starting up, it sets up an interrupt table. Each entry of the table points to a bit of code inside the operating system. When interrupts happen, which is controlled by the CPU, it looks at this table and calls the code. There are various interrupts, such as dividing by zero, invalid code, and some operating system defined ones.

This is how the user process talks to the kernel, such as if it wants to read/write to the disk or something else that the operating system kernel controls. An operating system will also set up a timer that calls an interrupt when it finishes, so the running code is forcibly changed from the user program to the operating system kernel, and the kernel can do other things such as queue up other programs to run.

From memory, when this happens the operating system kernel has to save where the code was, and when the kernel has finished doing what it needs to do it restores the previous state of the program. Thus the program doesn't even know that it was interrupted.

The process can't change the interrupt table for two reasons, the first is that it is running in a protected environment so if it tries to call certain protected assembly code then the cpu will trigger another interrupt. The second reason is virtual memory. The location of the interrupt table is at 0x0 to 0x3FF in real memory, but with user processes that location is usually not mapped, and trying to read unmapped memory will trigger another interrupt, so without the protected function and the ability to write to real RAM, the user process can't change it.

share|improve this answer
4  
The interrupts aren't defined by the operating system, they are given by hardware. And most current architectures have special instructions to call the operating system. i386 used a (software generated) interrupt for this, but it isn't done that way anymore on its successsors. –  vonbrand Jul 4 at 13:20
2  
I know that the interrupts are defined by the cpu, but the kernel sets up the pointers. I possibly explained it badly. I also thought that linux used int 9 to talk to the kernel still, but maybe there are better ways now. –  Programmdude Jul 5 at 1:56
    
This is a fairly misleading answer although the notion that preemptive schedulers are driven by timer interrupts is correct. First it's worth noting that the timer is in hardware. Also to clarify that "save ... restore" process is called a context switch and mostly involves saving all of the CPU registers (which includes the instruction pointer), among other things. Also, processes can effectively change interrupt tables, this is called "protected mode", which also defines virtual memory, and has been around since the 286 - a pointer to the interrupt table is stored in a writable register. –  Jason C Jul 5 at 6:34
    
(Also even the real mode interrupt table has been relocatable - not locked to the first page of memory - since the 8086.) –  Jason C Jul 5 at 6:36
1  
This answer misses a critical detail. When an interrupt fires, the CPU doesn't switch to the kernel directly. Instead, it first saves the existing registers, then switches to another stack, and only then is the kernel called. Calling the kernel with a random stack from a random program would be a rather bad idea. Also, the last part is misleading. You won't get an interrupt "trying" to read unmapped memory; it's simply impossible. You read from virtual addresses and unmapped memory simply has no virtual address. –  MSalters Jul 6 at 22:36

The OS kernel gets control back from the running process due to CPU clock interrupt handler, not by injecting code into the process.

You should read about interrupts to get more clarification about how they work and how OS kernels handle them and implement different features.

share|improve this answer
    
Not just the clock interrupt: any interrupt. And also mode change instructions. –  Gilles Jul 4 at 8:30

Multi-tasking does not require anything like code injection. In an operating system like Windows, there is a component of operating system code called the scheduler which relies on a hardware interrupt triggered by a hardware timer. This is used by the operating system to switch between different programs and itself, making it all seem to our human perception to happen concurrently.

Basically, the operating system programs the hardware timer to go off every so often... perhaps 100 times a second. When the timer goes off, it generates a hardware interrupt - a signal which tells the CPU to stop what it's doing, save its state on the stack, change its mode to something more privileged, and execute the code it will find in a specially designated place in memory. That code happens to be part of the scheduler, which decides what should be done next. It might be to resume some other process, in which case it will have to perform what is known as a "context switch" - replacing the entirety of its current state (including virtual memory tables) with that of the other process. In returning to a process, it has to restore all of the context of that process, and then return from the interrupt - restoring its privilege mode and execution state from the stack, and continuing that process.

The "specially designated" place in memory does not have to be known by anything but the operating system. Implementations vary, but the gist of it is that the CPU will respond to various interrupts by performing a table lookup; the table's location is at a specific place in memory (determined by the hardware design of the CPU), the contents of the table is set by the operating system (generally at boot time), and the "type" of interrupt will determine which entry in the table is to be used as the "interrupt service routine".

None of this involves "code injection"... it is based on code contained in the operating system in co-operation with hardware features of the CPU and its supporting circuitry.

share|improve this answer

I think the closest real-world example to what you describe is one of the techniques used by VMware, Full virtualization using binary translation.

VMware acts as a layer underneath one or more simultaneously executing operating systems on the same hardware.

Most of the instructions being executed (e.g. in ordinary applications) can be virtualized using the hardware, but an OS kernel itself makes use of instructions that cannot be virtualized, because if the machine code of the guess OS were executed unmodified it would "break out" of the control of the VMware host. For example, a guest OS would need to run in the most privileged protection ring, and set up the interrupt table. If it were allowed to do that, VMware would have lost control of the hardware.

VMware rewrites those instructions in the OS code before executing it, replacing them with jumps into VMware code that simulates the desired effect.

So this technique is somewhat analogous to what you describe.

share|improve this answer

There is a method similar to what you describe: co-operative multitasking. The OS does not insert instructions, but each program must be written to call OS functions which may choose to run another of the cooperative processes. This has the disadvantages you describe: one program crashing takes out the whole system. Windows up to and including 3.0 worked like this; 3.0 in "protected mode" and above did not.

Pre-emptive multitasking (the normal kind these days) relies on an external source of interrupts. Interrupts override the normal flow of control and usually save the registers out somewhere, so the CPU can do something else and then transparently resume the program. Of course, the operating system can change the "when you leave interrupts resume here" register, so it resumes inside a different process.

(Some systems do rewrite instructions in a limited way on program load, called "thunking", and the Transmeta processor dynamically recompiled to its own instruction set)

share|improve this answer
    
AFAICR 3.1 was cooperative as well. Win95 was where the preemptive multitasking came in. Protected mode mainly brought isolation of address space (which does improve stability, but for largely unrelated reasons). –  cHao Jul 7 at 4:33
    
Thunking does not re-write or inject code into the application. The loader that is modified is OS based and not a product of the application. Interpretive languages which are compiled such as using JIT compilers do not modify the code, nor injects anything into the code. They translate source code into an executable. Again, this is not the same as injecting code into an application. –  Dave Gordon Jul 7 at 11:32
    
Transmeta took x86 executable code as its source, not an interpretive language. And I've thought of one case in which code is injected: running under a debugger. X86 systems usually overwrite the instruction at the breakpoint with "INT 03", which traps into the debugger. On resume the original opcode is reinstated. –  pjc50 Jul 7 at 12:39
    
Debugging is hardly how anyone runs an application; beyond that of the developer of the application. So I don't think that really helps the OP. –  Dave Gordon Jul 8 at 12:04

There are a variety of cases in which an operating system might "inject code" into a program. The 68000-based versions of the Apple Macintosh system builds a table of all segment entry points (located immediately preceding the static global variables, IIRC). When a program starts, each entry in the table consists of a trap instruction followed by the segment number and offset into the segment. If the trap is executed, the system will look at the words after the trap instruction to see what segment and offset is required, load the segment (if it isn't already), add the start address of the segment to the offset, and then replace the trap with a jump to that newly-computed address.

On older PC software, although this wasn't technically done by the "OS", it was common for code to be built with trap instructions instead of coprocessor math instructions. If no math coprocessor was installed, the trap handler would emulate it. If a coprocessor was installed, the first time a trap is taken the handler will replace the trap instruction with a coprocessor instruction; future executions of the same code will use the coprocessor instruction directly.

share|improve this answer
    
The FP method is still in use on ARM processors, which unlike x86 CPU's do still have FP-less variants. But it's rare as most ARM use is in dedicated devices. In those environments it's typically known whether the CPU will have FP capabilities. –  MSalters Jul 6 at 22:40
    
In neither of these cases did the OS inject code into the application. For the OS to inject code it would need a license by the software vendor to "modify" the application which it doesn't get. OS's DO NOT inject code. –  Dave Gordon Jul 7 at 11:24
    
@DaveGordon Trapped instructions can be reasonably said to be the OS injecting code into the application. –  Gilles Jul 8 at 17:53
    
@MSalters Trapped instructions happens commonly in virtual machines. –  Gilles Jul 8 at 17:54

protected by Community Jul 8 at 17:52

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.