Types of Operating Systems

Types of Operating System

Modern computer operating systems may be classified into three groups, which are distinguished by the nature of interaction that takes place between the computer user and his or her program during its processing. The three groups are called batch, time-sharing and real-time operating systems.

Batch Processing Operating System

In a batch processing operating system environment users submit jobs to a central place where these jobs are collected into a batch, and subsequently placed on an input queue at the computer where they will be run. In this case, the user has no interaction with the job during its processing, and the computer’s response time is the turnaround time the time from submission of the job until execution is complete, and the results are ready for return to the person who submitted the job.

Time Sharing

Another mode for delivering computing services is provided by time sharing operating systems. In this environment a computer provides computing services to several or many users concurrently on-line. Here, the various users are sharing the central processor, the memory, and other resources of the computer system in a manner facilitated, controlled, and monitored by the operating system. The user, in this environment, has nearly full interaction with the program during its execution, and the computer’s response time may be expected to be no more than a few second.

Real-time Operating System (RTOS)

The third class is the real time operating systems, which are designed to service those applications where response time is of the essence in order to prevent error, misrepresentation or even disaster. Examples of real time operating systems are those which handle airlines reservations, machine tool control, and monitoring of a nuclear power station. The systems, in this case, are designed to be interrupted by external signals that require the immediate attention of the computer system. These real time operating systems are used to control machinery, scientific c instruments and industrial systems. An RTOS typically has very little user-interface capability, and no end-user utilities. A very important part of an RTOS is managing the resources of the computer so that a particular operation executes in precisely the same amount of time every time it occurs. In a complex machine, having a part move more quickly just because system resources are available may be just as catastrophic as having it not move at all because the system is busy.

Multiprogramming Operating System

A multiprogramming operating system is a system that allows more than one active user program (or part of user program) to be stored in main memory simultaneously. Thus, it is evident that a time-sharing system is a multiprogramming system, but note that a multiprogramming system is not necessarily a time-sharing system. A batch or real time operating system could, and indeed usually does, have more than one active user program simultaneously in main storage. Another important, and all too similar, term is “multiprocessing”.

Multiprocessing System

A multiprocessing system is a computer hardware configuration that includes more than one independent processing unit. The term multiprocessing is generally used to refer to large computer hardware complexes found in major scientific or commercial applications. Multiprocessor system is simply a computer that has more than one  CPU on its motherboard. If the operating system is built to take advantage of this, it can run different processes (or different threads belonging to the same process) on different CPUs.

Networking Operating System

A networked computing system is a collection of physical interconnected computers. The operating system of each of the interconnected computers must contain, in addition to its own stand-alone functionality, provisions for handing communication these additions do not change the essential structure of the operating systems.

Distributed Operating System

A distributed computing system consists of a number of computers that are connected and managed so that they automatically share the job processing load among the constituent computers, or separate the job load as appropriate particularly configured processors. Such a system requires an operating system which, in addition to the typical stand-alone functionality, provides coordination of the operations and information flow among the component computers.

Free-Space Management

Free-Space Management

Another important aspect of disk management is keeping track of and allocating free space.

Free space management can be done by:

1.      Bit Vector

·         One simple approach is to use a bit vector, in which each bit represents a disk block, set to 1 if free or 0 if allocated.

·         Fast algorithms exist for quickly finding contiguous blocks of a given size

·         The down side is that for example, a 40GB disk requires over 5MB just to store the bitmap.

2.      Linked List

·         A linked list can also be used to keep track of all free blocks.

·         Traversing the list and/or finding a contiguous block of a given size are not easy, but fortunately are not frequently needed operations. Generally the system just adds and removes single blocks from the beginning of the list.

·         The FAT table keeps track of the free list as just one more linked list on the table.

3.      Grouping

·         A variation on linked list free lists is to use links of blocks of indices of free blocks. If a block holds up to N addresses, then the first block in the linked-list contains up to N-1 addresses of free blocks and a pointer to the next block of free addresses.

4.      Counting

·         When there are multiple contiguous blocks of free space then the system can keep track of the starting address of the group and the number of contiguous free blocks. As long as the average length of a contiguous group of free blocks is greater than two this offers a savings in space needed for the free list.

5.      Space Maps

·         Sun's ZFS file system was designed for HUGE numbers and sizes of files, directories, and even file systems.

·         The resulting data structures could be VERY inefficient if not implemented carefully. For example, freeing up a 1 GB file on a 1 TB file system could involve updating thousands of blocks of free list bit maps if the file was spread across the disk.

·         ZFS uses a combination of techniques, starting with dividing the disk up into ( hundreds of ) metaslabs of a manageable size, each having their own space map.

·         Free blocks are managed using the counting technique, but rather than write the information to a table, it is recorded in a log-structured transaction record. Adjacent free blocks are also coalesced into a larger single free block.

·         An in-memory space map is constructed using a balanced tree data structure, constructed from the log data.

·         The combination of the in-memory tree and the on-disk log provide for very fast and efficient management of these very large files and free blocks.

File Allocation Methods

File Allocation Methods

There are three major methods of storing files on disks: contiguous, linked, and indexed.

1.      Contiguous Allocation

Contiguous Allocation requires that all blocks of a file be kept together contiguously. Performance is very fast, because reading successive blocks of the same file generally requires no movement of the disk heads, or at most one small step to the next adjacent cylinder.

Problems can arise when files grow, or if the exact size of a file is unknown at creation time:

o    Over-estimation of the file's final size increases external fragmentation and wastes disk space.

o    Under-estimation may require that a file be moved or a process aborted if the file grows beyond its originally allocated space.

o    If a file grows slowly over a long time period and the total final space must be allocated initially, then a lot of space becomes unusable before the file fills the space.

A variation is to allocate file space in large contiguous chunks, called extents. When a file outgrows its original extent, then an additional one is allocated. ( For example an extent may be the size of a complete track or even cylinder, aligned on an appropriate track or cylinder boundary. ) The high-performance files system Veritas uses extents to optimize performance.

2.      Linked Allocation

·         Disk files can be stored as linked lists, with the expense of the storage space consumed by each link. ( E.g. a block may be 508 bytes instead of 512. )

·         Linked allocation involves no external fragmentation, does not require pre-known file sizes, and allows files to grow dynamically at any time.

·         Unfortunately linked allocation is only efficient for sequential access files, as random access requires starting at the beginning of the list for each new location access.

·         Allocating clusters of blocks reduces the space wasted by pointers, at the cost of internal fragmentation.

·         Another big problem with linked allocation is reliability if a pointer is lost or damaged. Doubly linked lists provide some protection, at the cost of additional overhead and wasted space.

·         The File Allocation Table, FAT, used by DOS is a variation of linked allocation, where all the links are stored in a separate table at the beginning of the disk. The benefit of this approach is that the FAT table can be cached in memory, greatly improving random access speeds.

3.      Indexed Allocation

Indexed Allocation combines all of the indexes for accessing each file into a common block ( for that file ), as opposed to spreading them all over the disk or storing them in a FAT table.

Some disk space is wasted ( relative to linked lists or FAT tables ) because an entire index block must be allocated for each file, regardless of how many data blocks the file contains.

Performance

·         The optimal allocation method is different for sequential access files than for random access files, and is also different for small files than for large files.

·         Some systems support more than one allocation method, which may require specifying how the file is to be used ( sequential or random access ) at the time it is allocated. Such systems also provide conversion utilities.

·         Some systems have been known to use contiguous access for small files, and automatically switch to an indexed scheme when file sizes surpass a certain threshold.

·         And some systems adjust their allocation schemes ( e.g. block sizes ) to best match the characteristics of the hardware for optimum performance.

Directory Implementation

Directory Implementation

Directories need to be fast to search, insert, and delete, with a minimum of wasted disk space.

Linear List

·         A linear list is the simplest and easiest directory structure to set up, but it does have some drawbacks.

·         Finding a file ( or verifying one does not already exist upon creation ) requires a linear search.

·         Deletions can be done by moving all entries, flagging an entry as deleted, or by moving the last entry into the newly vacant position.

·         Sorting the list makes searches faster, at the expense of more complex insertions and deletions.

·         A linked list makes insertions and deletions into a sorted list easier, with overhead for the links.

·         More complex data structures, such as B-trees, could also be considered.

Hash Table

·         A hash table can also be used to speed up searches.

·         Hash tables are generally implemented in addition to a linear or other structure

File-System Implementation

File-System Implementation

File systems store several important data structures on the disk:

·         A boot-control block, ( per volume ) or the boot block in UNIX or the partition boot sector in Windows contains information about how to boot the system off of this disk. This will generally be the first sector of the volume if there is a bootable system loaded on that volume, or the block will be left vacant otherwise.

·         A volume control block, ( per volume ) or the master file table in UNIX or the superblock in Windows, which contains information such as the partition table, number of blocks on each filesystem, and pointers to free blocks and free FCB blocks.

·         A directory structure ( per file system ), containing file names and pointers to corresponding FCBs. UNIX uses inode numbers, and NTFS uses a master file table.

·         The File Control Block, FCB, ( per file ) containing details about ownership, size, permissions, dates, etc. UNIX stores this information in inodes, and NTFS in the master file table as a relational database structure.

There are also several key data structures stored in memory:

·         An in-memory mount table.

·         An in-memory directory cache of recently accessed directory information.

·         A system-wide open file table, containing a copy of the FCB for every currently open file in the system, as well as some other related information.

·         A per-process open file table, containing a pointer to the system open file table as well as some other information. 

Some of the interactions of file system components when files are created and/or used:

·         When a new file is created, a new FCB is allocated and filled out with important information regarding the new file. The appropriate directory is modified with the new file name and FCB information.

·         When a file is accessed during a program, the open( ) system call reads in the FCB information from disk, and stores it in the system-wide open file table. An entry is added to the per-process open file table referencing the system-wide table, and an index into the per-process table is returned by the open( ) system call. UNIX refers to this index as a file descriptor, and Windows refers to it as a file handle.

·         If another process already has a file open when a new request comes in for the same file, and it is sharable, then a counter in the system-wide table is incremented and the per-process table is adjusted to point to the existing entry in the system-wide table.

·         When a file is closed, the per-process table entry is freed, and the counter in the system-wide table is decremented. If that counter reaches zero, then the system wide table is also freed. Any data currently stored in memory cache for this file is written out to disk if necessary.

Partitions and Mounting

·         Physical disks are commonly divided into smaller units called partitions. They can also be combined into larger units, but that is most commonly done for RAID installations and is left for later chapters.

·         Partitions can either be used as raw devices ( with no structure imposed upon them ), or they can be formatted to hold a filesystem ( i.e. populated with FCBs and initial directory structures as appropriate. ) Raw partitions are generally used for swap space, and may also be used for certain programs such as databases that choose to manage their own disk storage system. Partitions containing filesystems can generally only be accessed using the file system structure by ordinary users, but can often be accessed as a raw device also by root.

·         The boot block is accessed as part of a raw partition, by the boot program prior to any operating system being loaded. Modern boot programs understand multiple OSes and filesystem formats, and can give the user a choice of which of several available systems to boot.

·         The root partition contains the OS kernel and at least the key portions of the OS needed to complete the boot process. At boot time the root partition is mounted, and control is transferred from the boot program to the kernel found there. ( Older systems required that the root partition lie completely within the first 1024 cylinders of the disk, because that was as far as the boot program could reach. Once the kernel had control, then it could access partitions beyond the 1024 cylinder boundary. )

·         Continuing with the boot process, additional filesystems get mounted, adding their information into the appropriate mount table structure. As a part of the mounting process the file systems may be checked for errors or inconsistencies, either because they are flagged as not having been closed properly the last time they were used, or just for general principals. Filesystems may be mounted either automatically or manually. In UNIX a mount point is indicated by setting a flag in the in-memory copy of the inode, so all future references to that inode get re-directed to the root directory of the mounted filesystem.

Virtual File Systems

·         Virtual File Systems, VFS, provide a common interface to multiple different filesystem types. In addition, it provides for a unique identifier ( vnode ) for files across the entire space, including across all filesystems of different types. ( UNIX inodes are unique only across a single filesystem, and certainly do not carry across networked file systems. )

·         The VFS in Linux is based upon four key object types:

o    The inode object, representing an individual file

o    The file object, representing an open file.

o    The superblock object, representing a filesystem.

o    The dentry object, representing a directory entry.

·         Linux VFS provides a set of common functionalities for each filesystem, using function pointers accessed through a table. The same functionality is accessed through the same table position for all filesystem types, though the actual functions pointed to by the pointers may be filesystem-specific. Common operations provided include open( ), read( ), write( ), and mmap( ).

File-System Structure

File-System Structure

Hard disks have two important properties that make them suitable for secondary storage of files in file systems:

(1) Blocks of data can be rewritten in place, and

 (2) They are direct access, allowing any block of data to be accessed with only (relatively) minor movements of the disk heads and rotational latency.

Disks are usually accessed in physical blocks, rather than a byte at a time. Block sizes may range from 512 bytes to 4K or larger.

File systems organize storage on disk drives, and can be viewed as a layered design:

·         At the lowest layer are the physical devices, consisting of the magnetic media, motors & controls, and the electronics connected to them and controlling them. Modern disk put more and more of the electronic controls directly on the disk drive itself, leaving relatively little work for the disk controller card to perform.

·         I/O Control consists of device drivers, special software programs ( often written in assembly ) which communicate with the devices by reading and writing special codes directly to and from memory addresses corresponding to the controller card's registers. Each controller card ( device ) on a system has a different set of addresses ( registers, a.k.a. ports ) that it listens to, and a unique set of command codes and results codes that it understands.

·         The basic file system level works directly with the device drivers in terms of retrieving and storing raw blocks of data, without any consideration for what is in each block. Depending on the system, blocks may be referred to with a single block number, ( e.g. block # 234234 ), or with head-sector-cylinder combinations.

·         The file organization module knows about files and their logical blocks, and how they map to physical blocks on the disk. In addition to translating from logical to physical blocks, the file organization module also maintains the list of free blocks, and allocates free blocks to files as needed.

·         The logical file system deals with all of the meta data associated with a file ( UID, GID, mode, dates, etc ), i.e. everything about the file except the data itself. This level manages the directory structure and the mapping of file names to file control blocks, FCBs, which contain all of the meta data as well as block number information for finding the data on the disk.

Common file systems in use include the UNIX file system, UFS, the Berkeley Fast File System, FFS, Windows systems FAT, FAT32, NTFS, CD-ROM systems ISO 9660, and for Linux the extended file systems ext2 and ext3 ( among 40 others supported. )

File Protection

File Protection

Files must be kept safe for reliability ( against accidental damage ), and protection ( against deliberate malicious access. ) The former is usually managed with backup copies. For later simple protection scheme is to remove all access to a file. However this makes the file unusable, so some sort of controlled access must be arranged.

Types of Access

·         The following low-level operations are often controlled:

o    Read - View the contents of the file

o    Write - Change the contents of the file.

o    Execute - Load the file onto the CPU and follow the instructions contained therein.

o    Append - Add to the end of an existing file.

o    Delete - Remove a file from the system.

o    List -View the name and other attributes of files on the system.

·         Higher-level operations, such as copy, can generally be performed through combinations of the above.

Access Control

One approach is to have complicated Access Control Lists, ACL, which specify exactly what access is allowed or denied for specific users or groups.

·         The AFS uses this system for distributed access.

·         Control is very finely adjustable, but may be complicated, particularly when the specific users involved are unknown. 

UNIX uses a set of 9 access control bits, in three groups of three. These correspond to R, W, and X permissions for each of the Owner, Group, and Others. The RWX bits control the following privileges for ordinary files and directories:

bit	Files	Directories
R	Read ( view ) file contents.	Read directory contents. Required to get a listing of the directory.
W	Write ( change ) file contents.	Change directory contents. Required to create or delete files.
X	Execute file contents as a program.	Access detailed directory information. Required to get a long listing, or to access any specific file in the directory. Note that if a user has X but not R permissions on a directory, they can still access specific files, but only if they already know the name of the file they are trying to access.

Windows adjusts files access through a simple GUI.

File-System Mounting

File-System Mounting

·         The basic idea behind mounting file systems is to combine multiple file systems into one large tree structure.

·         The mount command is given a filesystem to mount and a mount point ( directory ) on which to attach it.

·         Once a file system is mounted onto a mount point, any further references to that directory actually refer to the root of the mounted file system.

·         Any files ( or sub-directories ) that had been stored in the mount point directory prior to mounting the new filesystem are now hidden by the mounted filesystem, and are no longer available. For this reason some systems only allow mounting onto empty directories.

·         Filesystems can only be mounted by root, unless root has previously configured certain filesystems to be mountable onto certain pre-determined mount points. ( E.g. root may allow users to mount floppy filesystems to /mnt or something like it. ) Anyone can run the mount command to see what filesystems are currently mounted.

·         Filesystems may be mounted read-only, or have other restrictions imposed.

·         The traditional Windows OS runs an extended two-tier directory structure, where the first tier of the structure separates volumes by drive letters, and a tree structure is implemented below that level.

·         Macintosh runs a similar system, where each new volume that is found is automatically mounted and added to the desktop when it is found.

·         More recent Windows systems allow filesystems to be mounted to any directory in the filesystem, much like UNIX.

Directory Structure - Types

Directory Structure

A disk can be used in its entirety for a file system.

Alternatively a physical disk can be broken up into multiple partitions, slices, or mini-disks, each of which become a virtual disk and can have its own filesystem. ( or be used for raw storage, swap space, etc. ). Or, multiple physical disks can be combined into one volume, i.e. a larger virtual disk, with its own filesystem spanning the physical disks.

Directory Overview

A directory is a container that is used to contain folders and file. It organizes files and folders into a hierarchical manner.

Directory operations to be supported include:

·         Search for a file

·         Create a file - add to the directory

·         Delete a file - erase from the directory

·         List a directory - possibly ordered in different ways.

·         Rename a file - may change sorting order

·         Traverse the file system.

1.      Single-Level Directory

Simple to implement, but each file must have a unique name.

2.      Two-Level Directory

·         Each user gets their own directory space.

·         File names only need to be unique within a given user's directory.

·         A master file directory is used to keep track of each users directory, and must be maintained when users are added to or removed from the system.

·         A separate directory is generally needed for system ( executable ) files.

·         Systems may or may not allow users to access other directories besides their own

o    If access to other directories is allowed, then provision must be made to specify the directory being accessed.

o    If access is denied, then special consideration must be made for users to run programs located in system directories. A search path is the list of directories in which to search for executable programs, and can be set uniquely for each user.

3.      Tree-Structured Directories

·         Each user / process has the concept of a current directory from which all ( relative ) searches take place.

·         Files may be accessed using either absolute pathnames ( relative to the root of the tree ) or relative pathnames ( relative to the current directory. )

·         Directories are stored the same as any other file in the system, except there is a bit that identifies them as directories, and they have some special structure that the OS understands.

4.      Acyclic-Graph Directories

When the same files need to be accessed in more than one place in the directory structure ( e.g. because they are being shared by more than one user / process ), it can be useful to provide an acyclic-graph structure. 

UNIX provides two types of links for implementing the acyclic-graph structure.

·         A hard link ( usually just called a link ) involves multiple directory entries that both refer to the same file. Hard links are only valid for ordinary files in the same filesystem.

·         A symbolic link, that involves a special file, containing information about where to find the linked file. Symbolic links may be used to link directories and/or files in other filesystems, as well as ordinary files in the current filesystem.

Windows only supports symbolic links, termed shortcuts.

5.      General Graph Directory

In general graph directory structure, cycles are allowed within a directory structure where multiple directories can be derived from more than one parent directory.
The main problem with this kind of directory structure is to calculate total size or space that has been taken by the files and directories.