The last few weeks over at The Progressive Blogger Alliance have been filled with people asking to be put on the Blogroll. The Blogroll - actually one of the first efforts that the PBA grew from, before the network even used a central node based on Drupal software - was discontinued a while back. A mixture of administrative trouble, technical glitches and a rumor that the Google bot may interpret Blogrolls as link farms (and punish the sites' rankings).

The last one I don't know about. If it is true, it might be best to leave it be. But the other two are fairly easily solved.

One problem with the present PBA blogroll is that it uses an external service, Blogrolling.com, whose free accounts are limited and which is not easy to administrate. It is for all purposes impossible to administrate in a group (with shared access and multiple permission levels), which is the philosophy the PBA and Drupal works on.

The solution is obvious: A Drupal module for a blogroll. The links will be fed to it by members - perhaps this could even be meshed with a custom profile field or the Homepage profile field - and the output page will be a Javascript application that prints the links.

--

Some extra convenient settings for fine-tuning this blogroll (multiple links, RSS feeds, blocking certain links from certain sites, subgroups that only link amongst themselves to keep the length down, etc) could be added as well.

--

Following this rough pipedream of a spec, the next step, naturally, is to see if this has been made before. If it hasn't, well... let's get going! ^_^

I just got back from a two-week vacation (visiting my parents). Sunday night here; tomorrow I'll go back to work. "Gah" just about sums it up.

The past two weeks were very relaxing however. For starters, I bought Myst IV Revelation, and it is absolutely great.

Atrus has a young daughter, Yeesha, who is abducted by her two older brothers. Apparently, they developed a very evil plan for vengeance against their father, and need to be stopped in time.

So far I've hit riddles in all three worlds that I can't solve: In Spire, a strange device supposedly generates frequencies that can shatter stone - but nothing happens when I try it. In Haven, another device should generate signals that a nearby group of monkeys should understand - but somehow, I'm not getting through to them. In Serenia, I am in a complicated mess of channels and irrigation pumps, which I just can't figure out. I guess this will take a while.

It was also my birthday two weeks ago (18th of July), and I'm now 19. I got some very nice presents - among them, a digital camera (yay!) and Mozart's Requiem on CD (even more yay!).

I notice that I'm getting tired, and it is exactly midnight now, so I should better head to bed. I need to work tomorrow, and I've gotten somewhat used to sleeping past 10 AM.

The exams are over. I got 2.7 on Data Communication, 2.7 on Statistics and 2.0 on Computer Architecture (which would be C+ and B, respectively). Now I have some time to myself. To celebrate that, I fiddled a bit with PHP and implemented a text search algorithm I'd learned. It's called the Boyer Moore Sunday algorithm, and works as follows:

• Begin with the offset 0.
• Test the substring of haystack that begins on offset:
• Begin with needle-offset 0.
• Compare the corresponding characters of needle and the substring of haystack.
• Continue with 4. until the string is found or there is a mismatch.
• If there is a mismatch, examine the character in haystack immediately after the substring.
• Take the last position of this character in needle, or -1 if it does not occur.
• Shift the offset in haystack to the right by the length of needle, and to the left by the position you just calculated.
• Continue with 2.

The implementation is here. Note that PHP differs from compiled languages in some syntax points - for example, a String is simply an array of characters and can be treated as such. The return value is typeless, it can be a boolean or an integer.

File Systems save their data in files.

They consist of:

• Files (duh)
• Folders
• Partitions

File contains data or program code. Folder groups files, partitions is a physical space on the hard drive, like a virtual drive.

Physical: One disk
Logical: A partition on a disk

File is the smallest unit that may be written to the peripheral memory.

Attributes:

Name, type, size, location

Additionally:

Accessed/modified/changed timestamps.

Access rights. owner.

Operations: open, close, create, delete, read, write, seek.

Folder groups files. A 1:n relation, can be implemented forwards (folder contains references to files) as in UNIX, DOS. Or backwards (each file contains reference to folder like in MySQL) as in BeOS, BFS.

A folder acts like a pointer, referencing certain physical locations on the drive.

Operations: open, close, create, delete (only empty, otherwise recursive), read, write. Has attributes like a files does.

Partitions: Up to now, we referenced a hard drive by cylinder, track and sector. Now we use logical partitioning.

The first partition is the MBR, Master Boot Record, telling BIOS where to look for the OS. Partitions usually consist of cylinders.

Partitions are used for dual-booting, logical structuring. Use of several file systems on one disk - partitions are completely independent of file systems, acting "outside" the system.

Maximal number of paritions: 63 on IDE, 15 on SCSI. Linux Loader LILO. Boot loader that can start several OSs and also boot from Logical Partitions. Usually, only primary partitions can be used.

BIOS loads MBR. MBR points to OS loader. (Boot sector).

There may be only one file system per partition - in fact, a partition's main attribute is its file system. File system is administrated by OS: OS thus needs a driver to handle a certain file system (Linux can't write NTFS usually).

Addendum: Had to leave because the exam was half an hour earlier than I thought. This section, fortunately, was not on the exam.

Two more topics: Memory Management and File Management.

Memory Management can use real/physical and virtual memory. MM is responsible for allocating the available memory and for controlling each task's access to the address space.

Real memory management

- means only the RAM memory physically available.
- "swapping" export.
- whole programs are exported at once to the swap file (Hard Drive)
- any task currently running is completely present in RAM, any that isn't is completely on the HD.
- Programs obviously can't be bigger than the RAM.

Virtual Memory Management

- The physical address space is extended with virtual memory on the hard drive (page file).

Problem with PMM: Fragmentation of the RAM.

Allocation/search for empty space: First Fit (the first free space gets taken), Next Fit (start searching on the spot where the last program was written (doesn't try to write time and again to a system part before), Best Fit (avoid fragmentation: Use the smallest memory block possible).

Disadvantages: Must have room for one whole program. A non-working process must be chucked out completely.

Virtual Memory Management

Along comes VMM. We make more space on the hard drive and then do the same thing a cache does, only in reverse. The cache is used to preload certain things we think will soon be needed into the small fast memory. The pagefile is used to save stuff we think won't be needed soon into the large slow memory (HD). Locality principles (spatial and temporal) still apply.

The process is known as "paging" because pages at one time are transferred. This is done by the OS without User Input.

Memory literally begins at address 0 and is technically infinite.

In VMM, the memory is like a new Level 4 cache lying below the other caches. Here, virtual memory is loaded into the DRAM cache. Uses a page table and pages and page frames.

Pre-paging: Preloads pages that are likely to be used soon.

Demand paging: Only when necessary.

Random depaging: Chuck out a random page when we need more physical space.

FIFO: First in first out. Oldest page is chucked out. Problem: Things that are constantly used have to be reloaded in regular intervals.

Least Recently Used. Problem: We need to keep track of access times, slowing down the whole thing. So you see, it's really like caching.

Page fault: A page is needed and missing. We first block the process, then use a page replacement algorithm to find the page to chuck. If it was changed, we need to writeback changes (remember writeback?) We load the page into the L4 Cache. Then we restart the blocked process.

Look-Ahead: Try to guess which page will be accessed latest and replace it. In practice, we are not clairvoyant unfortunately.

Look-Back: Much easier. Except we need to keep track, as mentioned.

Pageflutter

A process with not enough pages may cause very many pagefaults. Worst is trying to access a page just chucked out. Processes with no locality do this. A lot of overhead results.

Page buffer: We constantly keep a certain number of free pages. Export is done ahead of time. We have won some time when pages must be rewritten.

Working set: The immediate pages that the process needs most often. Hard to predict. Must not be too large (overlap) or too small (pagefluttering). Also requires timetracking.

Pages can be replaced locally or globally, ie from one process to another.

Local allocation means one space for each program. Can be either equal or dynamic.

Advantage: More flexible use of resources, no fragmentation, no limit on process size.

Disadvantage: A lot of overhead for pagetables. CPU overhead too.

UNIX uses demand paging. Swapping is also used on occasion.

Yay yay yay.

This might be the absolutely last entry. It takes up the entire second section of the course, but it's far shorter.

An operating system is the software that controls the execution of other programs on the hardware and also administers the various resources.

This includes service programs (txt editor etc)

The hierarchy looks like this:

Application
|
V
Compiler
|
V
Operating System
|
V
Firmware
|
V
Hardware

The OS forms the connection between the higher, more abstract levels of the machine and the lower, more physical ones.

The OS is responsible for ensuring correct data, robust applications (ie, avoiding crashes). It must be easily maintainable and usable. It also should use the hardware resources efficiently, allowing high speed.

DIN 44330: OS forms the foundation of the system, controls and monitors processes.

Process Handling

Implicit/literal addressing: The load command contains no target register (accumulaor). Or: All addresses are explicitly named.

Relative/absolute addressing: We either handle offsets or absolute addresses.

Indirect addressing. The cell we address contains another address that is then used to get the cell we want.

One process is also called a Task.

A job is a single action that is performed once - like a mouse click on a certain button.

Multitasking: Several processes run at once. Preemptive: OS decides when to switch. Cooperative: Process decides when to hand over the reins. Latter very susceptible, of course.

Multiuser: Like multitasking, but different users may initiate different tasks that also can't see each other.

Process hierarchies: A process spawns a child process. In UNIX, these tasks are handled with multitasking. In DOS, the parent process waits for the child to finish.

The different states of a process: Calculating, blocked, ready. A process can go from calculating to either, but it cannot begin calculating from blocked, nor can it be blocked while ready.

Thread: A logical, single unit within a task. A thread shares the memory of its task parent, but is handled as its own task with a certain CPU allotment. Several threads of the same task may communicate. Processes may not (directly that is).

Multiprocessing/Multithreading: Several threads may run at once (not shared, but at the same time on multiple CPUs). ASMP, SMP. Asymmetric dedicates one CPU to the system. Symmetric shares program code and system processes on different CPUs.

The process table tracks information about different processes.

Synchronizing processes isn't easy. Dependancies can crop up unexpectedly.

-----

Synchronizing with Lock

If several processes run the same Shellscript at once, there may be a part of the Shellscript that has to run "alone" without any interference.

Thus, we invent what MySQL calls the Table Lock: We first check if the lock is active. If it isn't, we activate it. Then we run, then we remove the lock.

UNIX uses the lockfile command for this.

Busy waiting: If the file is locked, we keep checking till it isn't.

Only one process may be in its critical block at one time. No assumptions about the processor (speed etc). Processes not in their critical block may not preempt other processes. Processes must not wait indefinitely before entering critical phase.

Semaphore bits are used to signal the entry and exit from critical blocks.

Deadlocks: Several processes somehow manage to wait for each other indefinitely.

Think of two philosophers next to each other. One grabs the fork, the other grabs the knife. Both are now waiting for the other to relinquish their grip on the cutlery implement, but neither is willing to let go (they're philosophers, they're stubborn).

Deadlocks can be ignored, recognized or avoided. Ignoring is the easiest of course.

Batch jobs must declare their required resources prior to starting. Further resources may not be locked down.

Round Robin: fair, but dumb algorithm. Small packets of time increase overhead, but larger pockets increase response delay.

Priority Scheduling: each process gets a priority score. This is allocated by the system either statically (at the beginning) or dynamically.

Processes with much user i/o get preference (improving user response time), high cpu usage is frowned on, waiting processes are ignored entirely. Priorities must be updated constantly.

Static priority works thuswise: The process gets a weight. When it has gotten a time share, its score is decreased, but it increases the faster the higher the time share is.

Shortest job first. If you know how long a batch job will take, execute the shortest first.

First come first served: May be bad.

Think of the supermarket queue. Have you had this situation where the housewife getting weekly supplies for her eight family members is before you in line, but waves you past because you only have a chocolate bar - or vice versa? Likewise. Utilitarianism here: Rather have the long job wait a short while than have the short job wait a long while.

We come to Pipelining. Pipelining is a way to improve the efficiency of a processor.

The idea is to execute several commands in parallel, thus using the resources more effectively. As mentioned previously, the command consists of several phases: Fetch, Read, Execute, Write.

In theory, four commands could be pipelines through the processor at once, each in a different phase.

Problems: Structure hazards (a command requires exlusive hardware access), data hazards (two commands share a data dependancy) and control hazards (conditional jumps that depend on earlier commands).

Solution for Control Hazard

- Since the problem hinges on conditional statements not being ready before the next command requires them, why not fill the intervening space with several independent commands? These commands may do something useful, avoiding the waste of cycles, while the condition test cycle is waiting for completion. Only when it is complete, the actual jump is performer.

- Other CPUs may try to predict the conditional jump - or, in case of multiple processors, even execute both at once. In the case of a long loop, for example, it may save much time to just assume the condition will return true and start the next cycle before the condition has actually been tested. The extra cycles that have to be discarded are less of a performance hit than it would have been to wait for the condition test in each cycle of the loop.

These solutions are implemented by the compiler as it translates the program to machine code.

Vector Computer

Vector Processors are optimized for, strangely enough, vector computing. A vector is like an array: It is a set of values of equal type. Calculations on a vector usually have to be performed on each element in turn - independently.

In a normal processor, this would require loading each cell of the vector into the register, loading the command that changes it, and making the change.

In a vector processor, the whole vector can be processed at once with a single command. The processor will see to it that the command is executed on all elements of the vector. Needless to say, this is much quicker.

Vectors are loaded into a "vector register" - all elements at once. Using pipelining, the independent operations are then applied to each element in turn.

We have four problems.

Backwards dependency and forwards anti-dependency.

1. A cell is dependent on previous cells that are not yet updated. This happens when several commands are in the vectorized loop, and an earlier command relies on previous values set later in the cycle, but in earlier cycles.

Think of vectorization as a reordering from

CYCLE 1 CMD A
CYCLE 1 CMD B
CYCLE 1 CMD C
CYCLE 2 CMD A
CYCLE 2 CMD B
CYCLE 2 CMD C
CYCLE 3 CMD A
CYCLE 3 CMD B
CYCLE 3 CMD C

into

CYCLE 1 CMD A
CYCLE 2 CMD A
CYCLE 3 CMD A
CYCLE 1 CMD B
CYCLE 2 CMD B
CYCLE 3 CMD B
CYCLE 1 CMD C
CYCLE 2 CMD C
CYCLE 3 CMD C

Suddenly, it becomes very important at what position in the cycle the command was. All earlier commands are executed before all later commands, and may not depend on them.

The two problems therefore are when a command assumes that another command later in the cycle was already executed for previous cycles (backward dependency) or when a command assumes that another command earlier in the cycle was not yet executed for later cycles (forward anti-dependancy).

Symmetric Multiprocessing

Several processors share the same memory and cache.

NUMA

Each CPU has its own memory.

Flynn

We finally come to the classification according to Flynn. This was developed back in '66 and is still the most popular thing today.

We describe only command and data streams.

Each can be Single or Multiple.

SISD (single instruction, single data) is the traditional von Neumann principle.

SIMD. Multiple data means that the processor can perform several calculations at once from the same command. A vector computer does this.

MISD. Effectively paradoxical, never implemented yet. The idea is to perform several instructions on the same set of data, which is operated on in a kind of assembly line. This may be used in:

MIMD. Several data and several instruction streams. Dual core or other multiple processor machines where the processors work independently, processing both their own commands and their own data. Highly scalable. Done by connecting several SISD processors.

Note to Google users:

If you actually want a good source, you'd be better off with Von Neumann architecture on Wikipedia.

We're getting close to the end. Note that I'm occasionally adding the German terms for some devices; this will help me remember them since the exam is, in fact, in German.

The von Neumann computer is divided into two distinct system parts: The CPU and the RAM memory. The rest (HD, input and output devices) are peripheral devices. CPU and memory are connected via two cables called "buses". The first is the address bus. It goes only in one direction; from the CPU to the memory. Here, the CPU sends requests for reading or writing certain memory cells.

The second is the data bus. It goes in two directions. Here, the memory sends read data back to the CPU, or the CPU sends data to write to the memory. The data bus is also connected to the peripheral devices.

CPU

The CPU is divided into the Control Unit (Steuerwerk), the Arithmetic Logic Unit (Rechenwerk) and the registers. Registers are high speed memory cells within the CPU that serve different functions. The Befehlszähler contains only the memory address of the next command. It is either incremented or - in case of a jump instruction like a loop or an if - is changed to a different value. The Befehlsregister contains the Word of Command itself (note that a "Word", in techspeak, is a code of a certain fixed bit length, in this case usually 16 bit long).

ALU

The ALU has two input registers which can be used to perform a certain arithmetic or boolean operation. The result is stored in the output register.

Commands

The CPU knows two types of command: Those involving only register operations, and those involving memory operations.

Three examples to illustrate:

Command Protocol

This is what the processor does with a command:

• Load the command addressed in the Befehlszähler from the memory into the Befehlsregister.
• Update the Befehlszähler (when exactly this is done with a conditional jump is another matter. Does it take another command cycle after the condition is tested to perform the jump?)
• Decode the command currently in the command register.
• If the command requires a memory cell (most do), find its address.
• Read the required cell into a register if necessary.
• Execute the command.
• Load the command addressed in... and so forth. This is done many millions of times each second. The life of a computer is a monotonous and stressful one.

Interpreter

The thing to note about these commands is that they are not hardwired into the computer. They are byte codes of data, which can be parsed and interpreted by any program. In effect, you can use Java to write a "virtual CPU" that interprets a certain program's code, looks up its memory accesses in a virtual sandbox memory (or allows it to access the physical memory) and acts in all ways like a hardware processor would, except not as fast due to the overhead.

Interpreters can be used at a much lower level too - at the operating system or even below it, extending the processor with "macros" that it interprets and passes on to the physical CPU. This allows for complex commands in the machine code that are executed by the interpreter without the user realizing the difference.

The advantage is the option of building a simpler (thus faster) CPU with fewer hardwired commands, while still allowing for a large and complex command set. The overhead is negligible - around 100%, which is very much balanced by the advantages.

RISKY KISS - er, RISC vs CISC

Can you tell it's 1 AM and I'm beginning to get tired?

There's a definite difference between

and

The latter is a so-called "high language", one that allows for very complex commands (for loops, arrays, even object-oriented programming). The first does only what you tell it to - step by tiny step, using only register cells and memory addresses. There is no reason why this should be any different - let the compilers worry about the machine code, let the humans write in a way that does not fry their brains.

This thought was not always prevalent.

In the late 70s, processors were made very complex. The mission was to close the gap between the high language and machine code, making it possible to write Assembly in the same way one would code Java.

Then, a new processor was developed. This implemented what was dubbed the RISC architecture, making use of only very few, simple commands as opposed to the CISC processors with their interpreters.

Naturally, the RISC processor required several times as many cycles to do what a CISC processor had a single command for. But the RISC processor needed no interpreter, which allowed it to decode commands up to ten times as fast.

I'm now using this blog to post summaries of the exam stuff, because somehow I memorize things by writing them down.

Input & Output

There are several different devices that connect the computer either to a user or another device. Input devices supply the computer with information, output devices are for transmitting or displaying information.

Output device - Screen

Older screens (CRT) contain a Cathode Ray Tube - otherwise known as an Electron Cannon. A cathode and an ring-shaped anode are used to fire a constant, narrow stream of electrons in a certain direction.

Two sets of electromagnetic fields are used to bend the ray vertically and horizontally. The ray then hits a screen made of a phosphorescent material - one that emits light when hit by electrons. In color screens, three different materials are used that emit blue, red and green light, which combine additively.

To prevent blurring of the image, a shadow mask is used that clearly defines the dots that may be hit by the ray. This can be a delta mask (arranged in triangles, losing a lot of the radiation and being therefore dimmer) or a slit mask (vertical slits, showing vertical lines on light, large surfaces and pixellating diagonal lines something dreadful).

Newer screens (LCD) use polarizing filters and liquid crystals. A backlight emits polarized light, which is - depending on the direction of the liquid crystal - either reversed or unchanged. If it is twisted, it can pass through the second, perpendicular polarization filter.

Other than that, the screen works in the same way - the polarized light hits a shadow mask, being allowed through in designated tri-color dots, which make up the image. The advantage: All dots are illuminated at once, eliminating flickering. The disadvantage: Each pixel requires three tiny transistors that determine the polarization of the crystal. If any of these 3*1024*768 transistors breaks or is faulty, the result is an off-color pixel (turning 378369 into, say, 378300, thus removing the blue part of the threebyte color).

Input device - keyboard

The keyboard constantly checks whether a key has been pressed. If it has, the key's scan code (the signal generated when the key makes contact) is stored in its buffer, and it sends an interrupt to the CPU.

When the key buffer is full, it emits that characteristic beep that you hear when you hold the alt-F4 key in frustration as the computer busily calculates the value of Pi to a billion digits.

Input device - Mouse

Older mouses (Trackball) have a small sphere (usually coated in rubber for better traction) that transmits the movement of the mouse on a surface onto two (three) wheels which then transmit their signal to the computer.

Newer devices can work wirelessly (also with infrared). Other mice use an optical sensor instead of a trackball, allowing for better resolution.

Output device - Printer

Some older printers use a typewheel, allowing them to print only certain characters. Others use a dot matrix (needles) - these are both referred to as "impact driven" since they collide with the paper quite roughly - allowing for carbon copies, but making them extremely noisy similar to a typewriter.

Inkjet printers spray ink onto the paper from a distance. This requires pressure behind a set of extremely narrow holes which allow the ink through. Needs to be cleaned with some regularity, and is susceptible to drying in if the printerhead is not "parked" in between printing.

Laser printers, finally, work by charging a photoelectric plate (or a cylinder), then discharging it with a laser beam (the parts of the plate that are hit are discharged). The discharged places then hold the toner powder (made of a mixture of wax or plastic and dry ink) on the cylinder, until it is transferred onto the page and fused on with heat. This is why large laser printers require a warmup phase, and why printouts are warm or even hot to the touch.

Continuous Flow

In this printer, ink is constantly flowing through the head. Drops are constantly being produced. If the drop should not be printed, an electromagnetic field diverts it into a driptray. Advantage: Very fast - relies on the electromagnetic field. Disadvantage: Uses ink. Heck of a lot of it.

Drop on Demand

Piezo

A small piezocrystal in the head can be made to vibrate with an AC current. The vibration literally hurls an ink drop out of the chamber. Epson uses this.

Bubblejet

The ink is heated over its boiling temparature. The sudden evaporation forces a drop out of the chamber. Canon and HP use this.

Input device - Scanner

Flatbed, Drum and Hand scanner. Work by shining light on the scanned object and analyzing it with photosensitive cells.

And that would be all in this chapter. Another 150 pages to go...

In 22.5 hours, I will be in the last exam this year - Computer Architecture. The topic is quite interesting, but hopelessly extensive. It also requires gratuitous memorizing, which isn't my forté.

Distinguish the four bus systems PCI, SCSI, USB and Firewire, naming three distinctive properties of each.

In other words, what I'm expected to memorize from the script is that:

• PCI has a 32 bit parallel transmission
• PCI has a signal frequency of 133 MHz
• PCI transmits 133 Mbit/s, version 2.0 twice that
• There are eight versions of the SCSI bus: SCSI-I, SCSI-II, Fast SCSI, Wide SCSI, Ultra SCSI, Ultra Wide SCSI, Ultra 2 SCSI and Ultra 160 SCSI. It starts at 5 Mbit/s and doubles for each version except II and Ultra, ending in 160 Mbit/s.
• SCSI reaches 3 meters, but as of Ultra Wide SCSI this has changed to 1.5 meters.
• USB cable can reach 5 meters
• A single USB host can service two devices, but by interconnecting hubs it is possible to connect up to 127 devices.
• A SCSI bus must be terminated (with a terminating resistor), and the distance between devices must be over 10 cm (of cable).
• USB can transmit up to 500 Mbit/s
• Firewire can reach 4.5 meters
• Firewire can currently transmit 400 Mbit/s, the new specification up to 1600 Mbit/s, and a new spec for 4800 Mbit/s is in planning
• Firewire can service 63 devices.

It's literally a jumble of trivia knowledge. Which is definitely going to be on the exam - it was on the practice exam as well.

Yay.

Edit on 2006-07-13: It was on the exam. In the exact same wording as it was phrased in the practice test. I'm one lucky SOB for learning this. And a paranoid one. Everyone else assumed this question was a random exception, and the real exam would make much more sense.