Memory v. Disk

Hardware v. Software

What is a Program?

A list of instructions. A precise definition of what is to be done, as opposed to an English language description of what is to be done. A precise description is an algorithm, a recipe that can be followed blindly by a machine.

A list of instructions to be executed one by one by a machine that has no memory of past instructions and no knowledge of future instructions.

There are many processes that we observe in nature (animal vision, language use, consciousness) and invent in culture (calculating prime numbers, sorting a list). Some we have converted to algorithms. Some remain in the domain of an English language description.

The Church-Turing thesis claims that "Any well-defined process can be written as an algorithm".

How is this Program, this list of instructions, to be ENCODED?

What (if any) is the difference between the MACHINE and the PROGRAM?
Many possibilities:

Hardware (mechanical/electronic) is SPECIALLY CONSTRUCTED TO EXECUTE THE ALGORITHM. All you do is turn the machine on. e.g. Searle's mechanical "Chinese Room" (Remember hardware does NOT have to be general-purpose. Hardware can encode ANY algorithm at all.)
Hardware is specially constructed to execute the algorithm, but there is some input data which is allowed to vary. This input data is READ at run-time by the machine. Custom hardware for an algorithm seems strange - we think of stock exchange / gambling customised devices - but really this is what watches, calculators, mobile phones, etc. are too.
Hardware is a general-purpose device, and the PROGRAM, as well as the input data, is read at run-time by the machine. e.g. Every normal computer (mainframe, PC, laptop). Even palmtops and children's toys are now programmable.
A general-purpose device implements a number of simple, low-level hardware instructions that can combine (sometimes laboriously) to run any algorithm. Program is written, say, in High Level Language like C++. Compiler translates this into low-level instructions for the particular hardware.
Why not write direct in the low-level instructions? You can, but then you can only run the program on that machine. If you write in a HLL, the same program can be recompiled into the low-level instruction set of a different machine, which is an automated process, and much easier than having to re-write the program from scratch.
One HLL instruction (x := x+y+5) may translate into many low-level instructions (find the memory location represented by "x", read from memory into a register, do the same with "y" into another register, carry out various arithmetic operations, retrieve the results from some further register, write back into a memory location).

CISC v RISC

There is a body of theory showing the minimal number of low-level instructions you need to be able to run any algorithm.

We can have pressure to:

Increase the number of hardware instructions - CISC model.
OBSERVE the system in operation. Anything done many, many times gets its own dedicated instruction in hardware (this is the history of Operating Systems).
Example: x86.
Decrease the number of hardware instructions - RISC model.
Simpler CPU runs faster. May not matter if executes higher number of low-level instructions if runs much faster.
Examples: Many.

As Operating Systems have evolved over the years, they constantly redefine the boundary between what should be hardware and what should be software.

The standard model for a Computer System

Program is kept until needed on some permanent medium (HARD DISK, DISKETTE, CD, DVD, FLASH DRIVE, TAPE).
To run the program, it is loaded into some temporary but faster medium (RAM). Temporary data structures and variables are created, and worked with, in this temporary medium.
In fact the CPU may not even work directly with this medium, but demand that for each instruction, everything that is needed is loaded temporarily into an even faster, volatile medium (REGISTERS). e.g. To implement X := X+1, where program variable X is stored at RAM location 100:
```
		MOV 	AX, [100]
		INC 	AX
		MOV 	[100], AX
```
We use special-purpose registers, customised for use with the CPU instruction set, and with fast direct access to the CPU.
The results of the program are output either to some temporary or permanent medium.
When the program terminates, its copy in the temporary medium is wiped, along with all of its temporary data and variables. The long-term copy still survives however, on the permanent medium it was originally read from.

Memory v. Disk

"Memory" is used by some people for all of the following.
I will use a more restricted definition:

"Memory" = The temporary (volatile) medium.
An unstructured collection of locations, each of which is read-write, randomly-accessible.
RAM = "working memory" = the fast, temporary medium that we actually run programs in. Reset every time we restart the computer.
- RAM may be cached for speed. See Cache memory.
- Video memory - dedicated to the display only.
"Disk" = The permanent (non-volatile) medium.
A more structured space than memory, formatted with a file system in place, where different zones of the disk have names and are separated from each other.
The permanent medium that we store programs and data files in.
- ROM - Read-only (or at least hard-to-rewrite) memory built-in to a computer (e.g. the basic code to load an operating system).

A sample computer: Asus Lamborghini VX5.
4 G memory.
1 G video memory.
Apparently 12 M cache memory.
1 T disk (in this case a flash drive).

Questions

If RAM was as fast as registers, would we use registers at all?

Or just reserve an area of RAM for the CPU's calculations? The CPU could work direct with program variables:
```
		INC 	[100]
```
But it seems that a large, expandable memory space could NEVER be as fast as a small, dedicated memory space tightly integrated with the CPU.
Also, in modern machines the circuitry does not exist to do arithmetic and logical operations on RAM. Only registers have this circuitry. RAM is currently designed only as a medium to send data to and receive data from registers. Adding this circuitry to every single RAM location would be quite an overhead, which is why the current, three-tier architecture has evolved.

If disk was as fast as memory, would we use memory at all?

It seems likely that a volatile medium will ALWAYS be faster than a permanent one, so the current two (or three)-tier system will survive.
But if disk speeds increase, we may see increasing usage of disk as an overflow of RAM (which would begin to adopt a role much like registers now).
Note that disk speeds have NOT increased as significantly as CPU and memory speeds.

If we have "permanent RAM", that retains its contents after power off, then in what sense is this not "disk"?

Basically, yes, it is disk (or could be used as disk, if formatted and structured as such).
ROM can be seen as a form of non-volatile memory. ROM and PROM can only be written once, so obviously are no good as a "disk".
EEPROM can be repeatedly written, but there are difficulties with using some forms of EEPROM as "disk".
Flash memory is a non-volatile read-write type of EEPROM that has been used as classic memory (unstructured).
And it can also be used as disk. On a PDA or smartphone you can format and structure a flash memory space, and keep a file system on it.
Disk: Flash memory is coming in as a possible replacement for PC/laptop hard disks. See solid-state drives.
Memory: Because Flash is still slower than volatile RAM, many systems further load the code into RAM to run it, and so the two-tier system survives, with flash memory now in the role of a smaller, more expensive, but much faster "disk", and now, in the context of this architecture, not "memory" any more.

For the whole history of computers, we needed all the speed we could get, which is why these complex, multi-tiered machines have evolved.

Mathematically, this multi-tier system is not necessary. Only a single medium is needed.

From the engineering point of view, it is doubtful if a single-tier system will ever come into existence, for the reasons above. But it is useful to think about the possibilities for different architectures, especially when later in this course we consider using disk as an overflow of memory, and memory as a cache for disk.

The multi-level Memory hierarchy

Compile-time, Load-time and Run-time

The standard model:

Program is written "in factory" in HLL, with comments, English-like syntax and variable names, macros and other aids to the programmer.

Program is then compiled "in factory" into an efficient, machine-readable version, with all of the above stripped, optimisations made, and everything translated and resolved as much as possible, so as little as possible needs to be done when it is run.

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.

Any change that has to be done while the algorithm has already started to run, is a change at "run-time".

Compile-time, Load-time and Run-time (continued)

Memory mapping (or binding)

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

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

	   do 10 times
		print(x)
		x := x+7

Obviously 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:

The programmer maps x to 7604 in the source code.
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)
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.
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.

Compile-time, Load-time and Run-time (continued)

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"