Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA170      CA216      CA249      CA318      CA651

w2mind.computing.dcu.ie      w2mind.org


OS structure

"Process" = A program running. Could be multiple copies of the same program running. (Multiple processes.)



Device speed

Recall History of OS.
What do we mean "I/O devices are slower than CPU" ?




Device controllers and Interrupts



CPU is kept free (responsive to user, able to run other code) while device I/O is going on.

Modern OS driven by interrupts.

Interrupts are to do with the massive asymmetry between CPU speeds and device speeds. They are how the OS program runs on hardware with slow devices.




Interrupts (IRQs) on Windows.
My Computer - Properties - Device Manager - View - Resources by Type - Interrupt Request (IRQ)




Examples of Interrupts



Does an infinite loop cause an interrupt?

Does an infinite loop quickly (or eventually) cause an interrupt?

The Halting Problem (Turing, 1936).

Might just be a long loop. We have no way of knowing.
But still, even if long loop, control must switch occasionally - time-slicing.
It is a timer interrupt that switches control. But loop runs forever, time-sliced.



Unsolved problems in mathematics.
Note that if you could detect an infinite loop in general, then could solve all problems of the form:

Does there exist a solution to f(n)
for n > t?
by asking the OS if the following:
repeat
 n := n+1
 test solution
until solution
is an infinite loop, or just a long loop? Then our OS could solve many of the world's great mathematical problems.
Many mathematical problems can be phrased as infinite-loop problems.



Note that many "infinite loops" actually terminate with a crash, because they are using up some resource each time round the loop. e.g. This program:

f ( int x )
{
 f(x);
}

f(1);
will eventually crash with a stack overflow.
This program however:
while true { }
will run forever, time-sliced.




Interrupts - Keeping the OS in charge

Interrupt idea is a way of periodically keeping the OS in charge so nothing runs forever without reference to the OS. e.g. In time-slicing, periodic timer interrupt to give OS a chance to do something else with the CPU.

Remember, the CPU is just looking for a stream of instructions to process, whether they come from the "OS" or from "user programs". When the OS "runs" a program, it points the CPU towards a stream of instructions in the user program and basically hands over control. How do we know program cannot now control CPU for ever?

Note: Interrupt does not necessarily mean that OS immediately attends to the process that sent it (in the sense of giving it CPU time). It just means the OS is now aware that that process wants attention. The OS will note that its "state" has changed.




CPU modes

CPU modes

There must be a concept of an "OS-type program" (which can do anything, including scheduling ordinary programs) and an "ordinary program" (which is restricted in what it can do on the machine).

The restrictions on the "ordinary program" are normally not a problem - they are basically just: "Other programs have to be able to run at the same time as you".

This obviously makes sense in a multi-user system, but in fact it makes sense on a PC as well. When you're writing a program and you make an error, you don't want your crashed program to be able to crash the whole OS. You still want to be able to turn to the OS (which should still be responsive) and say "terminate that program".

Code is executed either in kernel/system/monitor mode or in user mode.

boot in system mode, load OS
when run program, switch to user mode

when interrupt, switch to system mode 
 and jump to OS code

when resume, switch back to user mode
 and return to next instruction in user code
Privileged instructions can only be executed in system mode.
e.g. Perhaps any I/O at all - user can't do I/O, user has to ask OS to do I/O for it (OS will co-ordinate it with the I/O of other processes).




Kernel mode or User mode?

  1. Parts of OS that are not scheduled themselves. Are always in memory. Operate in kernel/system mode. This part of the OS is called the kernel.
    Includes:
    • memory management
    • process scheduling
    • device I/O

    
    
  2. Parts of OS that can be scheduled. Come in and out of memory. Operate in user mode.
    Includes:
    • command-line
    • GUI
    • OS utilities

    Parts of OS that could be in either of the above:

    • file system
    • network interface

    
    
  3. Applications. All scheduled. Come in and out of memory. Operate in user mode.




Windows has both kernel-mode drivers and user-mode drivers.
From Microsoft driver developer manual.




Memory protection

Basic idea is that there is such a thing as a "bad" memory access.
User process runs in a different memory space to OS process (and other processes).

On multi-process system (whether single-user or multi-user) each process has its own memory space in which (read-only) code and (read-write) data live. i.e. Each process has defined limits to its memory space:



Q. Even if there are no malicious people, process memory areas need to be protected from each other - Why?


Above, each process has two registers - a base register and a limit register.
e.g. The base register for process 2 has contents 5200000. Its limit register has contents 3200000.
And then every memory reference is checked against these limits.
A simple model would look like this:


When reference is made to memory location x:

if x resolves to between base and (base+limit)
  return pointer to memory location in RAM 
else
  OS error interrupt
 


Q. Load values into base or limit registers are privileged instructions. Why?

As we shall see, in fact memory protection has evolved far beyond this simple model.





Map of memory



Looking at memory use on Windows in Task Manager.



Click "Resource Monitor" in the above and you get further breakdowns. (See "Memory" tab)
Hover over items to see definitions.






Compile-time, Load-time and Run-time

The transformations made to the program from the code written by a human to instructions executed by the CPU.

  1. Compiled program (e.g. typical use of C++, Java):
    1. Program typically written "in factory" in HLL, with comments, English-like syntax and variable names, macros and other aids to the programmer.
    2. Program is then compiled "in factory" into an efficient, machine-readable version, with all of the above stripped, optimisations made, and everything at "compile-time" translated and resolved as much as possible, so as little as possible needs to be done when it is run.
    3. At different times, on different machines, and with different other programs already running, the user will "launch" or "run" a copy of this compiled program. Any further translation that could not be done at compile-time will now be done at this "load-time". Then the algorithm itself actually starts to run.
    4. Any change that has to be done while the algorithm has already started to run, is a change at "run-time".

  2. Interpreted program (e.g. typical use of Javascript, Shell):
    1. No compilation step. Source code itself is read at "load-time".



Memory mapping (or binding)

Consider what happens with the memory allocation for a program's global variables.

Programmer defines global variable "x". Refers to "x" throughout his High-Level Language code:

	   do 10 times
		print(x)
		x := x+7
Clearly when the program is running, some memory location will be set aside for x and the actual machine instructions will be:
	   do 10 times
		read contents of memory location 7604 and print them
		read contents of loc 7604, add 7, store result back in loc 7604

How "x" maps to "7604" can happen in many ways:
  1. The programmer maps x to 7604 in the source code.

  2. Compile-time. If x is mapped to 7604 at this point (or before) then the program can only run in a certain memory location. (e.g. DOS - single user, single process)

  3. Load-time. The compiler might maps x to "start of program + 604". Then when the program is launched, the OS examines memory, decides to run the program in a space starting at location 7000, resolves all the addresses to absolute numerical addresses, and starts running.

  4. Run-time - even after the program has started, we may change the mapping (move the program, or even just bits of it, in memory), so that next time round the loop it is:
    	read contents of memory location 510 and print them
    	read contents of loc 510, add 7, store result back in loc 510
    
    Obviously, OS has to manage this!
    User can't. Programmer can't. Even Compiler designer can't.




Questions

Question - Why is it not practical for the OS to say to a user on a single-user system: "I'm sorry, another program is occupying memory space 7000-8000. Please terminate the other program before running your program"

Question - Why is it not practical for the OS to say to a user on a multi-user system: "I'm sorry, another program is occupying memory space 7000-8000. Please wait until the other program terminates before running your program"

Question - Why can't program writers simply agree on how to divide up the space? Some programs will take memory locations 7000-8000. Other programs will take locations 8000-9000, etc.

Question - The user's program has started. The OS needs to change what memory locations things map to, but binding is done at load-time. Why is it not practical for the OS to say to the user: "Please reload your program so I can re-do the binding"

Question - Why is it not practical to say to a user: "Please recompile your program"




Virtual Machine (VM)



Virtual machine



Running Linux inside Windows with VMware.
I use this kind of thing in DCU labs to teach system administration of an imaginary multi-machine network all running on one machine.
Image from here.




Java Virtual Machine

Java is a language designed for a machine that does not exist, but that can be emulated on top of almost any machine. Java runs on a virtual piece of "hardware", the Java virtual machine.

Promises:

  1. Portability. Write an application once, run everywhere.
  2. Run code from Internet on client-side. Even though from a site with different hardware, they will run on your hardware.


Java is a HLL. It is "compiled" to a "virtual" instruction set called Java bytecodes. These run on Java VM, where they are actually mapped to native hardware instructions.



What language is OS written in?

OS'es are written mainly in HLL, with some Assembly in Kernel.
Assembly fast but hardware-specific.
HLL much more portable, much easier to write/debug/change/maintain.

C / C++ does, however, allow you directly embed Assembly instructions within it.



Is Assembly needed?

Assembly is faster. But not needed everywhere.


Another reason to stick with HLL:
Modern compilers have smart optimisers:
Compiler often has a -optimise switch to analyse the HLL code to generate faster Assembly code.




Part of the Linux OS source. Written in C.
This is part of init/main.c in Linus Torvalds' Linux source.



Feeds      HumphrysFamilyTree.com

Bookmark and Share           On Internet since 1987.