Basic workout on 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".

In the debate about the possibility of Artificial Intelligence, some disagree that the Turing model of an algorithm is elastic enough to capture consciousness and other mental processes, and therefore they will (when understood) represent a new type of "algorithm". No such new type of algorithm has ever been presented though.

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

(1) 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.)
(2) 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.

(3) Hardware is a general-purpose device (a "Turing machine"), 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).
There is a body of theory showing the minimal number of low-level instructions you need to be able to run any algorithm.

(3) is what we're used to, but it's not the only model.

Also, we can have minimalist Turing machines, or complex Turing machines. We can have pressure to:

Increase the number of hardware instructions - CISC model. OBSERVE the system in operation. Anything done 1 million times gets its own dedicated instruction in hardware (this is the history of Operating Systems).
Decrease the number of hardware instructions - RISC model. Simpler CPU runs faster. Doesn't matter if executes more low-level instructions occasionally. RISC model tends to have won (Pentium).

[Footnote: Technically, a Turing machine has infinite memory.]

As new Operating Systems are invented and modified 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, FLOPPY DISK, CD-ROM, MAGNETIC TAPE, PUNCH CARDS).
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.

Definitions

"Memory" = The temporary (volatile) medium. An unstructured collection of locations, each of which is read-write, randomly-accessible.
"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.

"Memory" = RAM = "working memory" = the fast, temporary medium that we actually run programs in. Reset every time we restart the computer. E.G. PC HAS 64 MB MEMORY.

Hard disk, floppy disks (diskettes) = the permanent medium that we store programs and data files in. E.G. PC HAS 10 GB HARD DISK. To some people this is "long-term memory" (or "primary and secondary memory") but this is confusing.

BE WARNED! - If you use "memory" I will assume you mean RAM.

We will ignore ROM, Cache memory, etc. for now. These are not important compared to this basic memory/disk, temporary/permanent distinction.
Computers basic question is NOT "What is difference between ROM and RAM?" No one needs to know that. It's just a stupid soundbite.
Computers basic question is "What is difference between memory and disk?"

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 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?

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 somebody is marketing "permanent RAM", that retains its contents in a power outage, 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 only by special hardware, not by programs, and can only be written in bulk. One could in theory allow the software control the EEPROM writer, and read/write in bulk, to form some kind of laborious, more expensive, slower, much smaller volume "disk".
You could do the same with a CD-ROM writer (if you were mad).
Flash memory (see also here) is a non-volatile read-write medium that has been used as classic memory (unstructured).
But recently it seems you can get storage of many MB, similar to the hard disk sizes of not so long ago, so it becomes feasible to format and structure a flash memory space, and keep a file system on it.
However, because it 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.

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"