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.
What (if any) is the difference between the MACHINE
and the PROGRAM?
Many possibilities:
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:
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.
MOV AX, [100] INC AX MOV [100], AXWe use special-purpose registers, customised for use with the CPU instruction set, and with fast direct access to the CPU.
"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.
INC [100]
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.
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".
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+7Obviously 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 7604How "x" maps to "7604" can happen in many ways:
read contents of memory location 510 and print them read contents of loc 510, add 7, store result back in loc 510Obviously, OS has to manage this!
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"