Guide to Multitasking Operating Systems:Fundamentals of Hardware Organization

This area covers the concept of a multi-level machine and the basics of hardware in computer systems

• Processors
• Memory
• Input/Output

Introduction to Computer Systems Organization

Hundreds of different kinds of computers have been designed and built during the evolution of the modern digital computer. Most have long been forgotten, but a few have had a significant impact on modern ideas. The following is a brief overview of some of the key historical developments, to get a better understanding of how we got where we are now.

The Zeroth Generation - Mechanical Computers(1642-1945)

The first calculating device, which could add and subtract, was built by Blaise Pascal(1623-1662) in 1642. It was entirely mechanical, using gears, and powered by a hand operated crank. Charles Babbage(1792-1871) designed designed and built what was dubbed, the analytical engine. It had four components: the store(memory), the mill(computation), the input section(punched card reader) and the output section(punched and printed output). The great advance of the analytical engine was that it was general purpose. It read instructions from punched cards and carried them out. The problem with this machine was that the precision needed to produce thousands of gears,cogs, and wheels was too much for nineteenth century technology.

In the early 40's, Howard Aiken of Harvard University, discovered Babbage's work and built out of relays the general purpose computer that Babbage had failed to build out of toothed wheels. Named Mark I, it had 72 words of 23 decimal digits each, and had a instruction cycle time of 6 seconds.

The First Generation - Vacuum Tubes(1945-1955)

The stimulus for electronic computers was World War II.

Give brief history of computers, i.e. 1st through 4th generation... Describe different types of computers, architectures(SISD,SIMD,MIMD)...

Introduction to the Multi-level Machine Concept

The traditional view of computers is likened to a 'black box' where program and data go in and output comes out.

Figure 1.1 View of a Computer as a "black box"

The program in this case is in machine language Since it is both difficult and tedious to program in machine language, people have developed languages that are easier for them to program in. But this language is not the language of the computer. It is necessary to have either an intrepeter to convert the level 2 language instructions to level 1 instructions of the hardware one at a time or to have a translator convert the program all at once to a program in which the computer can understand. This is the notion of a virtual machine in which the programmer is unaware of the complexities of the levels below that of which one is programming at.

Figure 1.2 The Virtual Machine Concept

A computer can be thought of as a multi-level machine having 6 levels. At the highest level, it is easiest for the programmer to develop algorithms for problem solving. The programmer is not concerned with details of the computer. As a programmer gets into increasingly lower levels, one knows more and more of how exactly a computer works.

Figure 1.3 A Programmer's Multi-Level View of a computer

Programs written in a computer's machine language(level 1) can be directly executed by the computer's electronic circuits(level 0), without any intervening interpreters or translators. These electronic circuits, along with the memory and input/output devices, form the computer's hardware. Hardware consists of tangible objects- integrated circuits, printed circuit boards, cables, power supplies, memories, printers, and monitors- rather than abstract ideas, algorithms, or instructions.

The Digital Logic Level

Gates and Boolean Algebra

A digital circuit is one in which only two logical values are present. Typically, a signal between 0 and 1 volt represents one value(e.g. binary 0) and a signal between 2 and 5 volts represents the other(e.g. binary 1). Voltages outside these two ranges are not permitted. Tiny elctronic devices, called gates, can compute various functions of these two-valued signals. These gates form the hardware basis on which all digital computers are built.

The details of how gates work inside is beyond the scope of this discussion, belonging to the device level, which is below our level 0. Nevertheless, we will digress ever so briefly to take a quick look at the basic idea, which is not difficult. All modern digital logic ultimately rests on the fact that a transistor can be made to operate as a very fast binary switch. In figure 1.4 shown below, (a) is a single bipolar transistor (the circle) embedded in a simple circuit. This transistor has three connections to the outside world: the collector, the base, and the emitter. When the input voltage, Vin, is below a certain critical value, the transistor turns off and acts like an infinite resistance, causing the output of the circuit, Vout, to take on a value close to Vcc, an externally regulated voltage, typically +5 volts. When Vin exceeds the critical value, the transistor switches on and acts like a wire, causing Vout to be pulled down to ground(by convention, 0 volts).

Figure 1.4 Construction of Simple Logic Gates

The important thing to notice is that when Vin is low, Vout is high, and vice versa. This circuit is thus an inverter, converting a logical 0 to a logical 1, and a logical 1 to a logical 0. The resistor is needed to limit the amount of current drawn by the transistor. The time required to switch from one state to another is typically a few nanoseconds.

In (b), two transistors are cascaded in a series. If both V1 and V2 are high, both transistors will conduct and Vout will be pulled low. If either input is low, the corresponding transistor will turn off, and the output will be high. In other words, Vout will be low if and only if both V1 and V2 are high.

In (c), the two transistors are wired in paralell instead of in a series. In this configuration, if either input is highm the corresponding transistor will turn off and pull the ouput down to ground. If both inputs are low, the ouput will remain high.

These three circuits, or their equivalents, form the three simplest gates. They are called NOT, NAND,and NOR gates, respectively. NOT gates are often called inverters; we will use the two terms interchangeably. If we now adopt the convention that "high"(Vcc volts) is a logical 1 and that "low"(ground) is a logical 0, we can express the output value as a function of of the input values. The conventional symbols used to depict these gates are shown below in figure 1.5, along with the functional behavior for each circuit.

Figure 1.5 Truth Table Diagrams

If the output signal of Figure 1.4(b) is fed into an inverter circuit, we get another circuit with precisely the inverse of the NAND gate-namely, a circuit whose output is 1 if and only if both inputs are 1. Such a circuit is called an AND gate; its symbol and functional description are given in Figure 1.5(d). Similarly, the NOR gate can be connected to an inverter to yield a circuit whose output is 1 if either or both inputs are 1 but 0 if both inputs are 0. The symbol and functional description of this circuit, called an OR gate, are given in Figure 1.5(e). The small circles used as part of the symbols for the inverter, NAND gate, and NOR gate are called inversion bubbles. They are often used in other contexts as well to indicate an inverted logical signal.

The five gates of Figure 1.5 are the principal building blocks of the digital logic level. From the foregoing discussion, it should be clear that the NAND and NOR gates require two transistors each, whereas the AND and OR gates require three each. For this reason, many computers are based on NAND and NOR gates rather than the more familiar AND and OR gates. (In practice, all the gates are implemented somewhat differently, but NAND and NOR are still simpler than AND and OR.) In passing, it is worth noting that gates may have more than two inputs. In principle, a NAND gate, for example, may have arbitrarily many inputs, but in practice more than eight inputs is unusual.

Although the subject of how gates are constructed belongs to the device level, it should be known that there are two major families of manufacturing technology because they are referred to frequently. The two major technologies are bipolar and MOS(Metal Oxide Semiconductor). The major bipolar types are TTL (Transistor- Transistor Logic), which has been the workhorse of digital electronics for years, and ECL (Emitter-Coupled Logic), which is used when very high speed operation is required.

MOS gates are 10 times slower than TTL and 100 times slower than ECL but require almost no power and almost no space, so large numbers of them can be packed together tightly. MOS comes in many varieties, including PMOS, NMOS, and CMOS, with new varieties continually appearing.

Boolean Algebra

To describe the circuits that can be built by combining gates, a new type of algebra is needed, one in which variables and functions can take on only the values 0 and 1. Such an algebra is called a Boolean algebra, after its discoverer, the English mathematician, George Boole(1815-1864).

Just as there are funtions in "ordinary" algebra, so are there functions in Boolean algebra. A Boolean function has one or more input variables and yields a result that depends only on the values of these variables. A simple function, f, can be defined by saying that f (A) is 0 if A is 1. This function is the NOT function of Figure 1.5(a).

Because a Boolean funtion of n variables has only 2^n possible sets of input values, the function can be completely described by giving a table with 2^n rows, each row telling the value of the function for a different combination of input values. Such a table is called a truth table. The table of Figure 1.5 are examples of truth tables. If we agree to always list the rows of a truth table in numerical order(base 2), that is, for two variables in the order 00,01,10, and 11, the function can be completely described by the 2^n-bit binary number obtained by reading the result column of the truth table vertically. Thus NAND is 1110, NOR is 1000, AND is 0001, and OR is 0111. Obviously, only 16 Boolean functions of two variables exist, corresponding to the 16 possible 4-bit result strings. In contrast, ordinary algebra has an infinite number of functions of two variables, none of which can be described by giving a table of outputs for all possible inputs because each variable can take on any one of an infinite number of possible values.

The Microprogramming Level

The boundary between hardware and software is not well defined and, furthermore, is constantly shifting. Early computers had instructions for arithmetic, Boolean operations, shifting, comparing, looping, and so on, that were all directly executed by hardware. For each instruction, a specific hardware circuit was present to carry it out. One could unscrew the back panel and point to the electrinic components used by the division instruction, at least in principle.

On a multilevel computer, it is no longer possible to isolate the division circuits because there are no division circuits. All the instructions available at the conventional machine level (e.g. instructions for arithmetic, Boolean, shifting, comparing, looping) are carried out one step at a time by an interpreter running at the microprogramming level. The modern day equivalent of looking for the division circuits is to get out a listing of the microprogram and look for that portion of it which interprets division instructions.

Although programs at any level may be carried out by an interpreter, and although this interpreter itself may also be executed by another interpreter, this hierarchy cannot go on indefinitely. At the bottom level, there must be a physical hardware machine, with integrated circuits, power supplies, and similar "hard" objects. In this section, we will study how the hardware components are controlled by the microprogram and how the microprogram interprets the conventional machine level.

Because the architecture of the microprogramming level, called the microarchitecture, is defined by the hardware, it is usually primitive and awkward to program. Timing considerations are frequently important, for example. It has been said that microprogramming is "the implementation of hopefully reasonable systems through interpretation on unreasonable machines."

The microprogramming level has a specific function: to execute interpreters for other (hopefully, more reasonable) virtual machines. This design goal naturally leads to an organization highly optimized toward fetching, decoding, and executing conventional machine instructions, and in some cases, more sophisticated instructions.

Processors

This topic covers different aspects of the CPU of a computer.

Introduction to the CPU

The Central Processing Unit(CPU) is the 'brain' of the computer. Its function is to execute programs stored in main memory by fetching their instructions, examining them, and then executing them one after another. The CPU is composed of several distinct parts.(see fig. 1.4) The control unit is responsible for fetching instructions from main memory and determining their type. The ALU performs operations such as addition and Boolean AND needed to carry out instructions.

fig 1.4 The organization of a simple computer with one CPU and two I/O devices

The CPU also contains small, high speed memory used to store temporary results and certain control information. This memory consists of a number of registers, each of which has a certain function. The most important register is the program counter(PC), which points to the next instruction to be executed. Also important is the instruction register(IR), which holds the instruction currently being executed. Most CPUs have general-purpose registers as well for level 2 and 3 programmers for storing intermediate results.

Instruction Execution

When a program is loaded into memory, the PC is initialized to hold the address of the first instruction of the program. Then, instructions are executed sequentially unless an instruction changes the value of the PC, which we would call loops or gotos.

fig 1.5 Basic Instruction Cycle of a CPU

Typical instructions are 1 word long, where for micro-processors, is generally 16 bits, or 2 bytes in size. There are different types of instructions. Generally, there is an op-code(the instruction itself), operand(s), and/or an address field, which is used for program control such as loops and jumps. Given the type of instruction, an instruction may be from 1 word to 4 words for typical CPU's that are used in micro-computers. The opcode itself may take 8 bits to specify, then depending on the type of operand, another memory location or register, the operand field may take from 3 bits to the size of a typical address, which may be 16 or 32 bits. Instead of the address of the loaction of operands, the actual values themselves may be stored in the instruction. The address field of an instruction may take the place of the operand(s) field, or may be held directly after the instruction in memory.

Immediate Addressing
_________________________
| op-code | constant    |   The operand itself is provided in the
-------------------------   instruction.
Direct Addressing - memory direct
_________________________
| op-code | address     |   The memory address of the operand is
-------------------------   provided in the instruction.
Register Addressing - register direct
_________________________
| op-code | reg. |      |   The operand is stored in the register
-------------------------   which is specified in the address field
                            of the instruction.
Indirect Addressing - memory indirect
_________________________
| op-code | address     |   The memory location which holds the
-------------------------   address of the operand is given in the
                            instruction.
Indirect Addressing - register indirect
_________________________
| op-code | reg. |      |   The register which holds the address
-------------------------   of the operand is specified in the
                            instruction.
Index Addressing
_________________________
| op-code | i reg. |offs.|  The address of the operand equals the
-------------------------   content of the specified index register
                            plus the offset value given in the
                            instruction.
Relative Addressing
_________________________
| op-code | | offset    |   The address of the operand equals the
-------------------------   content of the PC plus the displacement.

fig 1.6 Generalized view of addressing modes for micro-processors

CPU Organization

Most CPU's today use the classical VonNeumann design in which there exists:

   A number of registers
   An ALU (Arithmetic and Logic Unit)
   A data path
   Multi-plexing of one input from many inputs 

fig. 1.7 Data path of a typical Von Neumann Machine using addition as an example

The registers feed into two ALU input registers, labeled A and B in the figure. These registers hold the ALU input while the ALU is computing. The ALU itself performs addition, subtraction, and other simple operations on its inputs, yielding a result in the output register. This output register can be stored back into a register, and from there, back into memory, if desired.

The Intel 80x86 Series

      Intel 8088
                             __________
Addressing  A0-A19 ---/20-  |          | -------- INTR
                            |          | -------- NMI
                            |          |           __ ___ ___
Data          D0-D7 ---/8-- |          | ---/2-- RQ/GT0-GT1  Bus Arbitration
                            |          |           ____
             __ __          |   8088   | -------- TEST
 Bus    |    S0-S2 ---/3--- |          |
Control |       __          |          | ----/4-- S3-S6    |Status
        |       RD -------- |          | ----/2-- QS0-QS1  |
        |     ____          |          |              __
        |     LOCK -------- | max mode | -------- MN/MX    |Miscellaneous
        |    READY -------- |__________| -------- RESET    |
                              /| /|  _|_
                               |  |   --
                              Clk +5v Gnd

fig. 1.8 Intel 8088 logical pinout

The Intel 8088 is an NMOS microprocessor sold in a 40-pin package. Internally, it has a 16-bit data path, but it reads and writes memory 8 bits at a time(i.e. the data bus width is 8 bits). It can address 1MB of memory. Whenever possible, the 8088 tries to fetch instructions in advance, so that when the next one is needed, it will already be available.

Memory

This topic covers different aspects of memory in a computer.

Introduction to Memory

The memory is that part of a computer where programs and data are stored. The basic unit of memory is the binary digit, called a bit. A bit may contain a 0 or a 1. Computers use the binary numbers because it has been the most reliable method for encoding digital information. As shown in figure 1.9 below, a logical binary zero corresponds to voltages between zero and one for an electrical signal, whereas a logical one corresponds to voltages between three and five volts. This arrangement makes for reliable distinction between the two logical values that comprise a computer's alphabet.

         5 _ _________________________________________
         4 _ ######################################### | High - 1
         3 _ ######################################### |

Voltage 2 _ ______________transition_________________

         1 _ _________________________________________
         0 _ ######################################### | Low - 0

 fig 1.9 Implementation of logical binary numbers in an electrical signal

Memories consist of a number of cells, or locations each of which can store a piece of information. Each cell has a number, called an address by which programs can refer to it. If a memory has n cells, it will addresses 0 to n-1. All cells in memory contain the same number of bits. If a cell consists of k bits, it can hold one of 2^k different bit combinations.

Computers also express memory addresses as binary numbers. If an address has m bits, the maximum number of cells directly addressable is 2^m. Most often, people see addresses as the octal or hexadecimal notation for these binary addresses.

Types of Memory

Memory can be defined as a part of computer that can hold information, either instructions or data. There are three basic logical categories into which memory falls: CPU memory(registers), primary memory(system RAM), and secondary memory(disks, tapes, CD-ROMs). CPU memory is used for maintaining the correct operation of the computer and as temporary storage for user or system programs. Primary memory is that memory with which the CPU fetches instructions from and stores data to(note: It is not uncommon to hear such phrases as 'The CPU writes data directly to the controller'. Though the controller, a device which acts as an interface between the CPU and the I/O device, may be receiving data 'directly' from the CPU, the controller is actually acting as if it were part of main memory by 'stealing' some of the main memories addresses. This is known as memory-mapped I/O. So, to the CPU, it thinks that it is working with primary memory). It is primary memory which most of us just call associate with the word "memory". Secondary memory can be thought of as the information stored on a physical medium that can be brought into the computer's primary memory as instructions or data. Most contemporary microcomputers have primary memory that is volatile, that is, once the power of a computer is lost, so is the contents of memory. Secondary memory is used for holding the operating system, user programs, and user data. When a computer is powered up, the necessary programs and data needed for the operation of a computer system are loaded from secondary memory. There are several different types of memory in a computer system:

1. Static RAM - Very fast, implemented in circuits that need only power to hold data. Very expensive to build also.
2. Dynamic RAM - Efficient, but implemented using capacitors which means that there is a need for refresh every few milliseconds to hold data.
3. ROM - Comes from factory 'pre-wired' hence the term read-only.

Note: Secondary storage such as magnetic disks also are a form of memory.

Note: PROMS, EPROMS, and EEPROMS are basically variations of ROM.

1. CPU memory - registers
2. Cache memory - static ram on CPU and/or on system board
3. System memory - dynamic ram
4. Secondary memory - stored on devices such as disk/tape

These three different types of memory, along with secondary storage media such as magnetic disks shows that there is a practical tradeoff between the type of memory that is used and how much.

      Speed (faster) ----------------------------------------------> (slower)
What:    Registers    CPU Cache   System Cache   Main Memory    Disk
Loc.:    CPU          CPU         Sys. Board     Sys. Board     Peripheal
Size(~): 120 bytes    8 Kbytes    128 Kbytes     8 Mbytes       80 Mbytes
Type:    Static       Static      Static         Dynamic        Magnetic
      Cost (expensive) -------------------------------------------- (cheap)

Memory Caching

There are basically two types of caches: disk and memory. Memory caching shall be explained here: Historically, CPU's have always been faster than memories. As memories have improved, so have CPU's, preserving the imbalance. What his means in practice is that after a CPU issues a memory request, it must remain idle for a substantial time while waiting for the memory to respond. It is not uncommon for a typical CPU to wait for 3 clock cycles. The problem is not in the technology but in the economics. Engineers know how to build memories that are as fast as CPU's but these are so expensive that equipping a computer with a megabyte or more is out of the question. Thus the choice comes down to having a small amount of fast memory or a large amount of slow memory.

There are techniques, known as caching, for combining a small amount of fast memory with a large amount of slow memory to get the speed of the fast memory(almost) and the capacity of the large memory at a moderate price. The small fast memory is called a cache and is under the control of the microprogram. For years, people have known that programs do not access their memories completely at random. If a given memory reference is to address A, it is likely that the next memory reference will be in the general vicinity of A. A simple example is the program itself. Except for jumps and procedure calls, instructions are fetched from consecutive locations in memory. Furthermore, most execution time is spent in loops, in which a limited number of instructions are executed over and over. The observation that the memory references made in any short time interval tend to use only a small fraction of instructions is called the locality principle. and forms the basis for all caching systems. The general idea is that when a word is referenced, it is brought from the large slow memory into the cache, so that the next time it is used, it can be accessed quickly.

[[Image:]]

fig. 1.10 Common arrangement of a cache design

If a word is read or written k times in a short interval, the computer will need 1 reference to slow memory and k-1 references to fast memory. The larger k is, the better the overall performance.

Input/Output

Disk

A hard disk contains one or more revolving platters that are stacked vertically, shown below. Each platter has both a top and bottom surface. Information is stored on each surface and is accessed by a read/write head.

Hard disk tracks and cylinders

Each surface is divided into thin magnetic tracks that are laid out as concentric circles. Tracks on each surface are numbered starting with track zero. The total number of tracks depends on the size of the platter.

Each surface of every platter looks identical; that is, each surface has the same number of tracks, and a track with a particular number(for example, track 9) occupies the same position on every surface. Because the platters are stacked vertically, all the tracks that have identical numbers are stacked as well. These identical tracks on all surfaces of all platters form a vertical cylinder. Reading an entire cylinder means reading all of its identical tracks. Each cylinder has the same number as its identical tracks, for example, cylinder 9 consists of all tracks 9.

Every track is further divided into sectors. A sector is the most basic addressable unit of storage on a hard disk. A sector normally holds 512 bytes of data. Sectors are numbered, and identical sectors are stacked vertically.

A specific sector on the disk is identified by three numbers: the number of the cylinder that contains the sector, a head number that identifies a specific platter, and the sector number within that track.

The FDISK in DOS and OS/2 divides a hard disk into areas called partitions, as shown below. A partition is a group of sectors in one or more cylinders. The starting and ending sectors are each identified by specific cylinder, head, and sector numbers. Information about every partition is recorded in the partition table in the Master Boot Record, which is also created by using the FDISK command.

Hard disk partitions

The main difference between a hard disk and a floppy disk is that the operating system treats the entire diskette space as one partition. Because there is only one partition, a diskette does not have a Master Boot Record.

The first sector of the disk(cylinder 0, track 0, sector 1) is reserved for the Master Boot Record. The first cylinder and first head are both numbered 0, but the first sector is called sector 1. Shown below is the layout of the Master Boot Record.

The figure shows that the Master Boot Record contains a loader program and a partition table. The loader program is used only by the ROM BIOS. At the end of the Power-On-Self-Test, ROM BIOS searches for a bootable diskette in the first diskette drive. If no diskette is in the first drive, ROM BIOS loads and executes the loader program that is in the Master Boot Record. This loader program uses the information in the Master Boot Record's partition table to search for a bootable disk partition.

The partition table contains four 16-byte structures, called partition entries, that describe the partitions on the disk. Shown below is a figure which defines the fields within a partition entry.

 Layout of Master Boot Record and Partition Table

A disk partition is divided up into 5 areas, shown below.

     Boot Sector
     File Allocation Table #1
     File Allocation Table #2
     Root Directory
     File Data Area

The FORMAT command creates and initializes these areas when the partition is formatted. The first area is the Boot Sector, which contains a loader program and a BIOS Parameter Block(BPB). The next two areas are the two copies of the File Allocation Table(FAT). The FAT describes the locations of file blocks in the disk. DOS maintains two copies of the FAT in case one gets damaged. The next area is the root directory. It is a table that contains a list of file entry structures describing files and directories listed under the file system root directory. The remaining area in the partition is reserved for file entries that are associated with files and subdirectories that are not in the root directory. This last area also contains the file data blocks-the actual data.

Boot Sector

The boot sector is created in the first sector of the disk partition when the partition is formatted using the FORMAT command. The boot sector consists of four fields, as shown below.

      JMP Instruction to Loader Program
      OEM Vendor Name
      BIOS Parameter Block(BPB)
      Loader Program

The first field contains a 1-byte jump instruction(0E9h or 0EBh) followed by a 8-bit or 16-bit displacement. The jump instruction is used to transfer control to the loader program located in the fourth field. The second field is an 8-byte vendor identification string that identifies the PC manufacturer and the DOS version number. The third field contains a data structure, the BPB, that describes the physical characteristics of the disk. The fourth field contains the loader program.

At the end of the Power-On-Self-Test(POST), ROM BIOS loads ands executes the loader program that is in the Master Boot Record. The master loader uses the partition address in the Master Boot Record's partition table to search for a bootable partition. Once it finds one, it then loads and executes the loader program that is in the boot sector of the bootable partition. The boot sector loader then loads one part of the DOS kernel(IBMBIO.COM), which in turn loads and executes the remaining parts of the DOS kernel(IBMDOS.COM, and COMMAND.COM).

BIOS Parameter Block

The BPB contains the following disk information:

   Number of bytes per sector
   Number of sectors per cluster
   Number of File Allocation Tables(normally two)
   Number of root directory entries(same number as the number of files and directories in the root directory)
   Media descriptor type, used for identifying the disk media type
   Number of sectors allocated for the FAT
   Number of heads on the disk
   Number of hidden sectors 

DOS uses the information in a BPB to access the corresponding hard disk or diskette. During system configuration, DOS reads the BPBs for every disk partition and diskette, and creates a linked list of tables. These tables contain the disk characteristics of all the disk partitions and diskettes configured to the system. DOS searches these tables the first time it accesses a disk partition or a diskette drive.

Root Directory

The root directory area contains a list of file entries. Each file entry is a 32-byte structure that describes a file or directory in the file system's root directory. Shown below is this file entry structure.(File entries for files and directories that are not in the root directory are located in the file data area of the partition)

      File Name
      File Name Extension
      Attribute
      Reserved
      Time
      Date
      Starting Cluster Number
      File Size

File Data Area

The file data area in the disk partition structure keeps the file data and the 32-byte file entries. The information in the file data area is maintained as either allocated or unallocated data blocks. Blocks that are associated with either a file or file entries form a chained list. DOS creates, updates, or deletes thes blocks when it processes files and directories.

File Allocation Table

DOS normally accesses disk data in a fixed number of sectors called a cluster. A cluster is the smallest unit of disk space that a file can have under DOS. A cluster contains from 4 to 8 adjacent sectors. The number of sectors per cluster is based on the size of the disk partition. Normally, a partition smaller than 16MB is given a 4KB cluster(8 sectors per cluster), while a partition of 16MB and above is given a 2KB cluster (four sectors per cluster).

Under DOS, files are saved on a disk as one or more blocks scattered thorughout the disk, as shown below. bitmap

A block is a collection of contiguous sectors. Each block has a unique starting and ending cluster numbers. The starting cluster of the first block of a file is recorded in the starting cluster field of the file entry.

To access a file, DOS must know the exact physical locations of the file blocks on the disk. The locations of the blocks are kept in the FAT. The DOS kernel continuously updates this table when files or directories are created, modified, or deleted. (A directory is simply a file that contains a list of files and subdirectories.) During a file read, DOS searches the FAT to find the physical location of each block it intends to read. The blocks are indentified by a group of cluster numbers. Each cluster points to a group of contiguous sectors in the disk. Once the sectors are identified, DOS can read or write these using the BIOS disk function (INT 13h) calls.

Video

A video monitor is a box consisting primarily of a CRT(Cathode Ray Tube) and its power supplies. The CRT contains a gun that can shoot an electron beam against a phosphorecent screen near the front of the tube, as shown below in Figure 1. Color monitors have three electron guns, one each for red, green, and blue. During the horizontal scan, the beam sweeps across the screen in about 50 usec, tracing out an almost horizontal line on the screen. Then it executes a horizontal retrace to get back to the left-hand edge in order to begin the next sweep. A device like this that produces an image line by line is called a raster scan device. If the horizontal retrace is not instantaneous, it is said to be boustrophedonic(like the way an ox plows a field: left-to-right then right-to-left; oxen do not have an instant retrace either).

Horizontal sweeping is controlled by a linearly increasing voltage applied to the horizontal deflection plates placed to the left and right of the electron gun. Vertical motion is controlled by a much more slowly linearly increasing voltage applied to the vertical deflection plates placed above and below the gun. After somewhere between 400 and 1000 sweeps, the voltages on the vertical and horizontal deflection plates are rapidly reversed together to put the beam back in the upper left-hand corner. A full screen image is normally repainted about 60 times a second. The beam motions are shown below in Figure 2.

To produce a pattern of dots on the screen, a grid is present inside the CRT. When a positive voltage is applied to the grid, the electrons are accelerated, causing the beam to hit the screen and make it glow briefly. When a negative voltage is used, the electrons are repelled, so they do not pass through the grid and the screen does not glow. Thus, the voltage applied to the grid causes the corresponding bit pattern to appear on the screen. This mechanism allows an electrical signal to be converted into a visual display.

Three kinds of terminals are in common use: character-map terminals, bit-map terminals, and RS-232-C terminals. They all can use any keyboard type, but they differ in the way the computer communicates with them and how the output is handled.

Character-map terminals

Most personal computers use the scheme shown in Figure 3, below, to display output on the monitor. (The keyboard is treated as a completely separate device.) On the video board, is a chunk of memory, called the video RAM, as well as some electronics for accessing the bus and generating video signals.

To display characters, the CPU copies them to the video RAM in alternate bytes. Associated with each character is an attribute byte, that describes how that character is to be displayed. Attributes can include its color, intensity, whether it is blinking, and so on. Thus, a screen image of 25 by 80 characters requires 4000 bytes of video RAM, 2000 for the characters and 2000 for the attributes. Some boards have more memory to hold multiple screen images.

The job of the video board is to repeatedly fetch characters from the video RAM and generate the necessary signal to drive the monitor. An entire line of characters is fetched at once so the individual scan lines can be computed. This signal is a high-frequency analog signal that controls the scanning of the electron beam that paints the characters on the screen. Because the board outputs a video signal, the monitor must be within a few meters of the computer.

Bit-map terminals

A variation on this idea is to have the screen not be regarded as a 25 by 80 array of characters, but as an array of picture elements, called pixels. Each pixel is either on or off. It represents one bit of information. On personal computers, the screen may typically contain 640 by 480 pixels. Terminals using a bit-map rather than a character map are called bit-map terminals. Many video boards can operate either as character-map or as bit-map terminals, under software control.

The same general idea is used as in Figure 3, except that the video RAM is just seen as a big bit array. The software can set any pattern it wants there, and that is displayed instantly. To draw characters, the software might decide to allocate, for example, a 9 by 14 rectangle for each character, and fill in the necessary bits to make the character appear. This approach allows the software to create multiple fonts, and intermix them at will. All the hardware does is display the bit array. Color can be handled using multiple arrays, sometimes called bit planes. With n, bit planes, one out of 2^n colors can be selected per pixel.

Bit-map terminals are commonly used to support displays containing several windows. A window is an area of the screen used by one program. With multiple windows, it is possible to have several programs running at the same time, each one displaying its results independent of the other ones