Disk Storage II : Physical Data Storage

• Components

  • Disk Drive and Disk "Pack"
  • Platters with (Typically) One Read/Write Head per Surface
  • Access Comb Used to Move All Read/Write Heads Towards or Away from the Centre of the Recording Surface

• A disk is composed of a stack of circular platters on a central spindle. The stack is rotated by a drive motor and read/write heads attached to a common comb are moved in and out to record data in different concentric circles ("tracks") on platter surfaces.

The disk subsystem is controlled by a "Disk IO Controller" board (in a microcomputer system) or by a "Disk Channel IO Processor" (on a mainframe computer system). The differences between these two are not significant at this point and we will treat them as being identical.

The disk surfaces are coated with a metalic oxide similar to that used on cassette music tapes or video tapes; data is magnetically recorded on these surfaces much the same way as on cassette or video tapes. The actual recording and "play-back" is done through a "read-write" head. Each surface has its own "read-write" head attached to a shared "access comb". When the disk drive is operating, the disk is constantly rotating; without moving the read-write heads, a circular path where data can be recorded or played-back passes under each head; this circular path is called a "track". The collection of tracks which can be thus accessed without moving the access comb (one track from each surface) is called a "cylinder". By moving the access comb in or out (towards or away from the spindle), the Disk IO Controller can store or recall data stored on different cylinders.

The Disk IO Controller copies blocks of data between main memory and the disk surface. These blocks of data are (generally) only a fraction of what could be stored on one track; each track is therefore divided up into smaller storage areas called "sectors", where each sector is large enough to hold one of these "blocks" of data.

Actually, use of the term "sector" implies that fixed sized storage area is used for all blocks of data stored on the disk; this is not true for some mainframe disk storage systems which use variable sized "physical blocks".

Physical I/O Information Requirements

Requirements

• Drive ID or Number
• Cylinder or Track Number
• Surface or Read/Write Head Number
• Physical Record or Sector Number
• Locating a specific sector of data on a disk requiresa cylinder number (cylinders are numbered from the outside edge toward the center starting at number 0), a surface (or read/write head) number, and a sector number.

  In order to perform disk IO, the processor must supply the Disk Controller with these three values (cylinder, surface, and sector numbers) plus a command (either "Read" or "Write") and the address of an area in memory to/from which the data block is to be copied.

Translation of Logical Data Storage Requirements

• It is important to realize that logical records are quite different from the data blocks stored in disk sectors. Very rarely will they be the same size. A particular file might have 80 character (byte) records, but that file might be stored on a disk which has 512 byte sectors. The first sector assigned to contain this file could hold 6 logical records plus 32 bytes of a 7th record (80x6 + 32 = 512).
• The translation of program requests to read or write records into physical level units (cylinder, surface, sector, etc.) is performed by the Logical Service Routines of the Operating System (you might want to review the introductory material on Operating Systems at this point). The actual transfer of the request to the Disk Controller is handled by Physical Service Routines of the Operating System.
• An area of major interest involves the processes by which logical requests (for records of files) can be turned into physical disk characteristics. How can the operating system tell where the space assigned to a file begins in terms of cylinders, surfaces, and sectors? How are the physical storage units (sectors) connected together when more than one is required for a file?
• Determining where a file begins on a disk (in physical terms) is part of a process called "Openning" the file. (For an output file, "Openning" involves finding a physical location where the file can be stored that is not already used by other files.)

  In order to determine where files start on a disk, each disk contains a table (at a fixed physical location on the disk). This table is typically called a Directory or VTOC (Volume Table Of Contents). The Directory (or VTOC) contains (among other values) a list of names for all files stored on the disk and, for each file, its starting location in physical units (or something that can be easily translated into physical units: cylinder, surface, sector).

  No two files on the same disk are allowed to have the same name; otherwise, the Operating System would not be able to tell which location should be used when a duplicated file name was supplied. Therefore, attempting to Open an Output file with a name already on the disk will cause a run-time error.

  Conversely, attempting to Open an Input file with a name which is not in the Directory will also cause a run-time error.

• When a file is created on a disk, previously unused sectors or "physical blocks" must be "assigned" or given to the file for its data storage. In order to reduce the overhead involved in assigning disk space and later managing it, many disk drive systems assign groups of sectors at a time. For example, under MS-DOS, disk space is assigned in groups of 2 or 4 sectors at a time (depending upon the specific disk drive).

  The size of the group of sectors assigned for a file is called the "allocation unit" size for the disk. A disk drive can only assign space for files as complete allocation units. If a sector contains 512 bytes and the allocation unit is 2 sectors, then a file with only 1 data byte will still use up 512x2 = 1024 bytes of disk space; in fact any file with between 1 and 1024 (inclusive) data bytes will use the same amount of space; a file with 1025 (to 2048) bytes will use 2 allocation units and so on.

• In order to be able to locate where a particular file's data has been stored on a disk, a special area of the disk is reserved and used as an index. This index is commonly called a VTOC (Volume Table Of Contents) or a Directory (depending upon the computer system). In any specific system, the VTOC/directory must always be located in the same place on the disk since, otherwise, a VTOC/directory would be needed to find the VTOC/directory. In almost every system, the VTOC/directory is located in the first few sectors on the disk.

  The VTOC/directory contains a list of names of files stored on the disk and for each its starting location in terms of physical disk units (cylinder, surface, and sector numbers). Typically, a VTOC/directory entry may contain other information such as the file size, when the file was created, and file "attributes". File "Attributes" may indicate such things as that the file is to be "Read Only" i.e. it can not be erase or overwritten.

• The easiest way to manage a file would be if it were stored on a disk in a series of contiguous (all together in one area) sectors. Such a system uses a "Contiguous Space Allocation" method. This would require that, before the file was create, the programmer specify how much space the file was going to need. The Operating System routines would need to know this in order to determine if a large enough space were available on the disk for the file.

  With Contiguous Space Allocation, if a programmer does not pre-request enough space, a run-time error will occur when the file runs out of space; if the programmer asks for too much space, a run-time error may occur because a big enough contiguous block may not exist. In addition, requesting more space than is needed wastes space on the disk which could be used by other files; in some systems, it is possible to ask for too much space and then give back whatever is not used after the file has been created, but this will only work if the file never "grows" or has data added to it and it does not get around the problem of finding an empty block as large as the initial request.

  
  Notice that if FILE.B were now deleted there would be 17 sectors of unused space, but not enough "contiguous" space to create a file of more than 9 sectors using "Contiguous Space Allocation".
• A modified form of Contiguous Space Allocation is used on IBM mainframe computers. The VTOC on an IBM mainframe's disk contains entries with "pointers" for up to 16 contiguous blocks. There need only be enough space to satisfy the space requested for the "primary" (first) block for the file to be created. If the primary allocation block is not enough, the Operating System will attempt to find up to 15 more "secondary" allocation blocks (one at a time) until the file has been fully created or no block can be found as large as requested for the "secondary" block allocation size. The sectors within each allocation block still must be contiguous, but the (up to) 16 allocation blocks do not need to be.

  Assuming that the IBM mainframe disk uses "sectors" for disk storage (which it does not) and assuming our earlier example with a block of 9 contiguous unused sectors and another block of 8 unused sectors and no other unused space: A request for

  
                 SPACE=(SECTOR,10,2)
    would fail;                 | |
              primary-----------+ +----------secondary
  
                 SPACE=(SECTOR,5,5)
    could handle a file up to 10 sectors;
  
  and
                 SPACE=(SECTOR,8,4)
    could handle a file up to 16 sectors.
  

• An alternative to "Contiguous Space Allocation" is to use "Chained Allocation". With "Chained Allocation" each allocation unit contains a separate "pointer" in addition to its data area. This pointer either contains the physical address (cylinder, surface, sector numbers) of the next unit allocated to this file, or a special "End" indicator. The Directory provides a "pointer" to the first allocation unit and each allocation unit from there on provides a pointer to the next one.
  
• As a common variation of this "Chained Allocation" scheme, the pointers are often collected into a single table instead of being physically attached to the data allocation unit. The first entry in the table is treated as the pointer from the first allocation unit, the second table entry as the pointer from the second, etc.

  This is the system used for disk storage by MS-DOS. The "Chain" table is called the disk's File Allocation Table (or FAT). Each FAT entry is either a 12-bit or 16-bit value (depending upon the size of the disk).

  MS-DOS terminology uses the term "cluster" instead of "allocation unit". File space clusters are normally 2 sectors of 512 bytes (although there is some variation with different disk types).

• EXAMPLE : MS-DOS DISK STRUCTURE (5.25" DSDD Diskette)
  This disk used 2 surfaces (0 and 1), with 40 tracks (0 to 39) on each surface and 9 sectors (1 to 9) of 512-bytes on each track.

  The "Boot" occupied the first sector (side 0, track 0, sector 1). This "Boot" record will be described in more detail later.

  There were 2 copies of the FAT incase one got damaged in some way. Each copy of the FAT occupied 2 sectors. Therefore the FAT copies used surface 0, track 1, sectors 2 to 5.

  The Boot sector could be viewed as an "allocation block" (or "cluster") number 0; and the FAT's and Directory as "allocation block" number 1; therefore file space begins with "allocation block" number 2.

  The Directory was 7 sectors long (where each sector was 512 bytes in length). Each directory entry is 32 bytes long (as described below) and therefore there were 112 entries in a 5.25" DSDD directory (7x512 = 32x112). This provided a limit to the maximum number of files/directories that could be stored in the "root" directory.

Major Components of Boot Sector

MS-DOS Directory Structure

• The "Primary name" and extension ("ext") are stored as ASCII encoded characters.
• "A" is a set of Attribute flags for the file (to be described soon).
  
  The Attribute Flag byte has the form:
  
  For example, a file with an Attribute Flag byte of 23h (00100011b) would be a "Read-Only", "Hidden" file which had been created or changed since the last backup (i.e. needed to be "Archived").
• "T" is the time the file was created or last changed.
• "D" is the date the file was created or last changed.
• "S" is the starting cluster number for this file.
• "Size" is the real size of this file in bytes.
  WARNING: The IBM PC stores multi-byte values backwards to what you might expect; so for example a 4-byte size of 1A E2 04 00 must be read as 0004E21Ah.

---





Sample FAT Structure

The File Allocation Table for a 5.25" DSDD diskette is composed of 12-bit entries. The method used for fitting 12-bit values into 8-bit bytes is somewhat awkward for humans but works nicely for the processor; two 12-bit cluster number pointers are fit into three 8-bit bytes. Pointers for clusters 0 and 1 are stored together in 3 bytes; pointers for clusters 2 and 3 are stored together in the next 3 bytes; and so on. Remember, the earlier "Warning" that values stored in bytes are stored backwards to what people normally expect; so a 3 byte value of 2B 70 0C should be read as 0C702Bh. Splitting this into two 12-bit values we get 0C7h and 02Bh; the 0C7h would go with the higher numbered cluster and the 02Bh would go with the lower number cluster of the pair.

The pointer value for cluster 0 is not a real pointer; instead this value is used to specify the disk type using a "Media Descriptor" value. The Media Descriptor for a 5.25" DSDD is 0FDh (for a 5.25" HD or a 3.5" 720K it's 0F9h(!???), etc.)

The pointer value for cluster 1 is always FFFh.

Certain pointer values are not used as real pointers to clusters but are reserved with special meanings:
• 000 --------> Unused cluster
• FF0-FF6 ----> Reserved cluster
• FF7 --------> Bad cluster
• FF8-FFFh ---> Last cluster of a file

SAMPLE FAT (First few entries only) 5.25" DSDD Diskette

               FD F0 FF 03 40 00 05 60 00 07 80 00 09 A0 00 FF 0F 00 
pointers for   +------+ +------+ +------+ +------+ +------+ +------+ 
clusters:       0 & 1    2 & 3    4 & 5    6 & 7    8 & 9   10 & 11

The clusters 2&3 pointers split up to give:
• cluster 2's pointer = 003 and cluster 3's pointer = 004
  i.e. cluster 2 is part of a file in which cluster 3 is the next cluster and cluster 4 is the cluster after that.
Cluster 10 is the last cluster of the file; and cluster 11 is unused.

---