19. Disk Storage : 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.

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 requires a 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. 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 an existing file begins on a disk (in physical terms) is part of an operating systsem process called "opening" the file. For an output file, "opening" involves the O/S 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 file system on the disk contains one or more index tables. This table is typically called a File Directory, or Root Directory, or even a Volume Table Of Contents (VTOC - from mainframes). The Directory 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 the disk physical units such as: cylinder, surface, sector).

  No two files on the same file system are allowed to have the same access pathname; otherwise, the Operating System would not be able to tell which location should be used when a duplicated file name was supplied.

• When a file is created on a disk, previously unused disk 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 called a "cluster". Later versions of Windows may have cluster sizes of as high as 64 sectors (32KB on a disk with 512-byte sectors).

  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.

  While larger cluster sizes make for fewer allocation table entries for large files, the large cluster sizes may waste a lot of disk space if you have many files. With a cluster size of 64 on a 512-byte sector disk (32KB cluster size), on average half a cluster goes empty at the end of every file, wasting 16KB at the end of every file. Many files, especially many small files, may waste huge amounts of disk space.

• 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 called "Extent-Based File Allocation" has been used on IBM mainframe computers and is now coming into use again on modern high-performance Linux file systems. 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, in case 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 in Little-Endian order, which appears in a DEBUG dump listing to be backwards to what you might expect; so for example a 4-byte size that displays in the dump as 1A E2 04 00 must be reversed and read as 0004E21Ah.