The Dynamics of Computer Programming

A computer program is a finite sequence of numbers, called machine words: P = {w(i): i≤n in N}. P has an associated memory address space A = {i: i≤n in N}. We formally write |P| = |A| = n, the cardinality of both collections.

An execution instance of P is the process of assigning the CPU's program counter register, denoted by PC, P's entry address E U A and tracing a subsequence of words in P, according to the rules of the CPU, with PC := PC + 1 or PC := NA, where NA in A U OS is a new address (positive or negative), referenced relatively or absolutely by the PC or the stack pointer SP (or both).

A return address is an address R in A U OS, which gets stored on the stack prior to the trace PC := NA.

Various subtasks by the program are finite subsequences of P, which are called the m subroutines of the program and are denoted by PS = {S(k): k≤m≤n}, where:

S(k) = {w(k,i): i≤[n/m], w(k,i)=w(j), some j}.

PS partitions P. That is, for m≤n: P = Uk=1mS(k)

P has a very specific property: If we assign the PC the address E and let the CPU execute P, the PC will eventually stabilize inside a specific subset EL of P, called the Event Loop, which catches and processes events according to user interaction.

Here's what a minimal EL, with |EL| = 3, looks like:

A w(A)
1: NEXTEVENT
2: JSR EVENT
3: BRA.S PC-2

The first instruction checks for a user event. If one exists, PC branches to the event. Then, PC branches back to address 1.

The Program Subroutines PS, share a common characteristic: If they are loaded correctly, they will always return the PC to EL, after completion of their associated task.

When the OS loads the program for execution and assigns the PC the program's entry point E, the stack of return addresses will be balanced and the PC will eventually stabilize inside EL. Subsequently, the OS simply follows the PC around in A U OS.

Since EL belongs to A, time-wise, there are only two possible outcomes for a correct program: Either the PC stays in A, or the PC returns to the OS. For example, if we assign the PC any non-entry address Z except E, the stack of the PC return addresses will contain Z's calling address at its top, which lies in the OS address space. The PC will execute any subroutines that lie between Z and the end of the subroutine normally. As soon as the PC reaches the end of the subroutine in whose address space lies Z, the PC will load Z's return address and hence return to the OS.

As such, the cases above can be likened to the machine having certain fixed points in A U OS, depending on where the program P(t) is loaded. These fixed points consist of two attractors, OS and EL and m repellers, the subroutines PS (for one program P(t)).

OS is a super-attractor, in the sense that a program P(t) has to always eventually terminate and return to the OS (after P(t) terminates for example). P(t)'s EL is a simple q-cycle attractor, where q = |EL|, since a program P(t) can stay loaded as long as the user wants. The subroutines S(k) are repellers, because no matter what they do, after they are done the program always eventually returns to EL.

When P(t) terminates (or when the time allocation by the OS for P(t) is over), the OS loads (or allocates time for) P(t+1), which loads EL. Then EL calls S(3), which in turn calls S(6), which in turn calls S(8). When S(8) terminates, it returns to S(6) and then back to S(3), which in turn when it terminates returns to EL (purple path). Then EL calls S(1) which calls S(5). When S(5) terminates, it returns to S(1), which in turn returns to EL. When P(t+1) terminates (or when the time allocation by the OS for P(t+1) is over), the OS loads (or allocates time for) P(t+2), etc.

The OS operating in Round Robin fashion therefore, is akin to a central 3D toroid structure which rotates, allocating time for each program according to the OS's central time-allocation routines:

OSRR.gif

OS running, allocating quantum time to 6 programs (EL) in a round-robin fashion (with jobs always terminating on time allocated), each of which has 6 subroutines S(1), S(2), ..., S(6), each of which has 6 sub-subroutines S(1,1), S(1,2), ..., S(1,6), etc. The three types of fixed points in a machine: OS (central point): Super-attractor. EL: 6-cycle Attractor. S(i,j,k,...): 6-cycle Repellers

When the PC is attracted by the fixed points EL, it performs a "cyclic vibration" of length |EL|. That is, within the allocated time for each P(t), the PC will cycle, taking the values {1, 2, ... |EL|}. The frequency of this "vibration" depends on the speed of the CPU. Whenever there is a vibration, there is friction. Whenever there is friction, there is heat. Hence, the CPU chip will get hot, something which is nicely revealed when one looks at a circuit board thermogram.

Back to Mathematics

Web Analytics

Valid HTML 4.01 Transitional