COMPUTER SCIENCE - COM 214 SUMMARISED

SECTION ONE

INTRODUCTION

In most applications, the file is the central element. Before data can be processed by a Computer-Based Information System (CBIS), it must be systematically organised. The most common method is to arrange data into fields, records, files and databases.

COMPUTER FILE

A Computer file can be defined as a collection of related data record .

ELEMENTS OF A FILE

A file consists of a number of records. Each record is made up of a number of fields and each field consists of a number of characters.

LOGICAL COMPONENTS OF FILE

The logical components deal with the real-world objects the data represent. These are field, record and file.

Field

A field is the basic element of data.

Record

A record is a collection of related fields that can be treated as a unit by some application program.

File

A file is a collection of related records.

FILE NAMING

Files provide a way to store information and read it back later. It can comprise the letters A-Z, numbers 0-9 and special characters $ # & + @ ! ( ) - { } ' ` _ ~ as well as space.   The only symbols that cannot be used to identify a file are * | < > \ ^ = ? / [ ] ' ; ,.

Naming Convention

Usually a file would have two parts with “.” separating them. The part on the left side of the period character is called the main name while the part on the right side is called the extension.

File Name Extension

A filename extension is a suffix to the name of a computer file applied to indicate the encoding convention or file format of its contents.

FILE ATTRIBUTES

Different file attributes are discussed as follow.

File Name

A file name helps users to differentiate between various files.

File Type

File types indicate which application should be used to open a particular file.

Location

This is a pointer to the device and location on that device of the file. As it is clear from the attribute name, it specifies where the file is stored.

Size

The size of a file is measured in bytes.

Protection

Protection attribute of a file keeps track of the access-control information that controls who can do reading, writing, executing, and so on.

Usage Count

This value indicates the number of processes that are currently using (have opened) a particular file.

Time, Date and Process Identification

This information may be kept for creation, last modification, and last use.

Attribute Values

In addition, all operating systems associate other information with each file. The list of attributes varies considerably from system to system.

SECTION TWO

FILE ORGANISATION, ACCESS AND MANAGEMENT

INTRODUCTION

Data files are organised so as to facilitate access to records and to ensure their efficient storage.

TYPES OF FILE

i. Master File:

This is a file that is fairly permanent in nature. It contains statistical identification or historical information which is used as a source of revenue. It is used regularly to show the current position of the file. E.g. payroll.

ii. Transaction File:

This is refers to as movement file, it is a collection of records of transaction process that are used to update a master file.

iii. Reference File:

Is a file with a reasonable amount of permanency, it is used to store information that may be frequently accessed.

iv. Program File:

When a program are keyed into the computer system. The program are usually stored on the file called program file.

v. Input/Output File:

When a program is written, we usually specify an area where the input and result (output) can be stored. These area that are open for these data are called input and output file respectively.

FILE ORGANISATION AND ACCESS METHODS

Here we use the term file organisation to refer to the structure of a file (especially a data file) defined in terms of its components and how they are mapped onto backing store.

File Organisation Criteria

In choosing a file organisation, several criteria are important:

• Short access time

• Ease of update

• Economy of storage

• Simple maintenance

• Reliability.

The relative priority of these criteria will depend on the applications that will use the file.

FILE ORGANISATION METHODS

The number of alternative file organisations that have been implemented or just proposed is unmanageably large. In this brief survey, we will outline five fundamental organisations.

• The pile/serial

• The sequential file

• The Random/Direct File

• The indexed sequential file

i. The Pile/Serial method

Data are collected in the order in which they arrive. Records are place on the storage device one after the other without any relationship between two adjacent records or with no regard for sequence.

ii. The Sequential File method

This is the arrangement of records on the storage device based on descending or ascending order ( a specified order or sequence) of a particular record key.

iii. Random/Direct File method

This is a method whereby records are placed into the disk at random i.e there is no obvious relationship between the two adjacent records.

iv. The Indexed Sequential File method

This method of file organisation combines both sequential and random access. Records are arranged on auxiliary storage in sequence of a record key as in sequential method.

ACCESS METHODS

Access method is any algorithm used for the storage and retrieval of records from a data file by determining the structural characteristics of the file on which it is used.

i. Serial Access

This means that each record can be located one after the other in the order in which they are stored. To get access to record number twenty (20) in a file, we have to go through or by pass the first nine records one after the other.

ii. Sequential Access

This allows file organised sequentially to be accessed serially in the order in which they are physically stored. Accessing sequentially means accessing a file in the sequential of the record key.

iii. Random/Direct Access

This method, record in a file can be accessed in any order with the help of the record key. It is also called direct access because any record can be accessed directly without searching through the order of physical arrangement.

,

iv. Dynamic access

this access method permits both sequential and random accessing to be carried out interchangeably on the same file with a program.

FILE MANAGEMENT

FILE MANAGEMENT SYSTEM

The file management system, FMS is the subsystem of an operating system that manages the data storage organisation on secondary storage, and provides services to processes related to their access.

Objectives of File Management System

• Data Management. Provide data management services to applications through convenient abstractions, simplifying and making device-independent of the common operations involved in data access and modification.

• Generality with respect to storage devices. The FMS data abstractions and access methods should remain unchanged irrespective of the devices involved in data storage.

• Validity. To guarantee that at any given moment the stored data reflect the operations performed on them, regardless of the time delays involved in actually performing those operations.

• Protection. To control Illegal or potentially dangerous operations on the data by enforcing a well defined data protection policy.

• Concurrency. To allow concurrent access to the data with minimal differences with respect to single-process access, save for access synchronization enforcement.

• Performance. The above functionalities should be offered achieving at the same a good compromise in terms of data access speed and data transferring rate.

File Management Functions

For an interactive, general purpose system, the under listed constitutes a minimal set of requirements:

• Each user should be able to create, delete, read, write, and modify files.

• Each user may have controlled access to other users’ files.

• Each user may control what types of accesses are allowed to the user’s files.

• Each user should be able to restructure the user’s files in a form appropriate to the problem.

• Each user should be able to move data between files.

• Each user should be able to back up and recover the user’s files in case of damage.

• Each user should be able to access his or her files by name rather than by numeric identifier.10

SECTION THREE

FILE DIRECTORIES

INTRODUCTION

Associated with any file management system and collection of files is a file directory. The directory contains information about the files, including attributes, location, and ownership.

Concept of File Directory

To keep track of files, the file system normally provides directories, which, in many systems are themselves files.

Contents of File Directory

File name, File Type, File organisation, Volume, Size used, Size allocation, Owner,

Access information, Date created, Date modified etc

File Directory Structure

The number of directories varies from one operating system to another.

In this section, we describe the most common schemes for defining the logical structure of a directory. These are:

• Single-Level Directory

• Two-Level Directory

• Tree-Structured Directory

• Acyclic Graph Directory

Single-Level Directory

In a single-level directory system, all the files are placed in one directory. This is very common on single-user operating systems.

Two-Level Directory

In the two-level directory system, the system maintains a master block that has one entry for each user. This master block contains the addresses of the directory of the users.

Tree-Level Structural Directories

In the tree-structured directory, the directory themselves are considered as files. This leads to the possibility of having sub-directories that can contain files and sub-subdirectories.

Path Names

When a file system is organised as a directory tree, some way is needed for specifying the filenames. The use of a tree-structured directory minimizes the difficulty in assigning unique names. The series of directory names, culminating in the file name itself, constitutes a pathname for the file.

FILE AND DIRECTORY OPERATIONS

A file is an abstract data type. To define a file properly we need to consider the operations that can be performed on files.

Operations on Files and Directories

The operating system provides systems calls to create, write, read, reposition, truncate and delete files. The following sub-units discuss the specific duties a file system must do for each of the following basic file operations.

File Operations

The following are various operations that can be done on file:

i. Creating a File

When creating a file, a space in the file system must be found for the file and then an entry for the new file must be made in the directory.

ii. Opening a File

Before using a file, a process must open it. The purpose of the OPEN call is to allow the system to fetch the attributes and list of secondary storage disk addresses into main memory for rapid access on subsequent calls.

iii. Closing a File

When all the accesses are finished, the attributes and secondary storage addresses are no longer needed, so the file should be closed to free up internal table space.

iv. Writing a File

To write a file, a system call is made specifying both the name of the file and the information to be written to the file. Given the name of the file, the system searches the directory to find the location of the file. The directory entry will need to store a pointer to the current block of the file (usually the beginning of the file). Using this pointer, the address of the next block can be computed where the information will be written.

v. Reading a File

To read a file, a system call is made that specifies the name of the file and where (in memory) the next block of the file should be put. Again, the directory is searched for the associated directory entry, and the directory will need a pointer to the next block to be read.

REPOSITIONING A FILE

When repositioning a file, the directory is searched for the appropriate entry, and the current file position is set to a given value. This file operation is also called file seek.

i. Truncating a File

The user may erase some contents of a file but keep its attributes. Rather than forcing the user to delete the file and then recreate it, this operation allows all the attributes to remain unchanged, except the file size.

ii. Deleting a File

To delete a file, the directory is searched for the named file Having found the associated directory entry, the space allocated to the file is released (so it can be reused by other files) and invalidates the directory entry.

iii. Renaming a File

It frequently happens that user needs to change the name of an existing file. This system call makes that possible. It is not always strictly necessary, because the file can always be copied to a new file with the new name, and the old file then deleted.

iv. Appending a File

This call is a restricted form of WRITE call. It can only add data to the end of the file. System that provide a minima set of system calls do not generally have APPEND, but many systems provide multiple ways of doing the same thing, and these systems sometimes have APPEND.

DIRECTORY OPERATIONS

When considering a particular directory structure, we need to keep in mind the operations that are to be performed on a directory.

i. Create a File: New files need to be created and added to the directory.

ii. Delete a File: When a file is no longer needed, we want to remove it from the directory. Only an empty directory can be deleted.

iii. Open a File: Directories can be read. For example, to list all files in a directory, a listing program opens the directory to read out the names of all the files it contains. Before a directory can be read, it must be opened.

iv. Close a File: When a directory has been read, it should be closed to free up internal table space.

v. Read a File: This call returns the next entry in an open directory. Formerly, it was possible to read directories using the usual READ system call, but that approach has the disadvantage of forcing the programmer to know and deal with the internal structure of directories. In contrast, READDIR always returns one entry in a standard format, no matter which of the possible directory structure is being used.

vi. Rename a File: Because the name of a file represents its contents to its uses, the name must be changeable when the contents or use of the file changes.

Renaming a file may also allow its position within the directory structure to be changed.

vii. Search for a File: We need to be able to search a directory structure to find the entry for a particular file.

viii. List a Directory: We need to list the files in a directory and the contents of the directory entry for each file in the list.

SECTION FOUR

FILE STORAGE MANAGEMENT

INTRODUCTION

The main purpose of a computer system is to execute programs. Those programs together with the data they access must be in main memory (at least partially) during execution. Since main memory is usually too small to accommodate all the data and programs permanently, the computer system must provide secondary storage to back up main memory.

FILE STORAGE MEDIA

There are two basic type of storage units

i. Primary storage

ii. Secondary storage

Primary storage:

Example is Random Access Memory (RAM).

Secondary storage: Most computer have attached with them one or more secondary storage devices so as data storage device for storing large amount of data. They can retain information regardless of whether or not power is supplied to them. They are very large storage capacity.

Main Memory

Main memory (sometimes known as internal memory or primary storage) is another name for RAM (and ROM). Main memory is usually used to store data temporarily.

Types of secondary storage media Magnetic storage

Magnetic Disk This is the common for database application because of it outstanding features of random access or direct access device.  Examples of magnetic disk are:

Floppy Disc

A removable, portable, cheap, low-capacity (1.44MB) storage medium.

Zip Disc

A removable and portable storage medium, similar in appearance to a floppy disk, but with a much higher capacity (100MB, 250MB or 750MB

Jaz Disc

A removable and portable storage medium based on hard-drive technology, with a large capacity (1GB or 2GB). Jaz discs are random access devices which were used for data back-up or moving large files between computers.

Hard Drives

Hard-drives have a very large storage capacity (up to 1TB). They can be used to store vast amounts of data.

Fixed Hard Drive

A hard-drive built into the case of a computer is known as ‘fixed’. Almost every computer has a fixed hard-drive.

Portable Hard Drive

A portable hard-drive is one that is placed into a small case along with some electronics that allow the hard-drive to be accessed using a USB or similar connection.

Magnetic Tape

The magnetic tape allows data to be serially stored on the tape surface.

Optical Storage Devices / Media

Why 'Optical'?

Optical storage devices save data as patterns of dots that can be read using light. A laser beam is the usual light source. The data on the storage medium is read by bouncing the laser beam off the surface of the medium.

Read-Only Optical Discs

Read-only optical discs have data written onto them when they are manufactured. This data cannot be changed.

CD-ROM

Compact Disc - Read-Only Memory (CD-ROM) discs can hold around 800MB of data. The data cannot be altered (non-volatile), so cannot be accidently deleted. CD-ROMs are random-access devices.

DVD-ROM

Digital Versatile Disc - Read-Only Memory (DVD-ROM) discs can hold around 4.7GB of data (a dual-layer DVD can hold twice that). DVD-ROMs are random-access devices.

Recordable Optical Discs

Recordable optical discs can have data written onto them (‘burnt’) by a computer user using a special disc drive (a disc ‘burner’).

CD-R and DVD-R

CD-Recordable (CD-R) and DVD-recordable (DVD-R) discs can have data burnt onto them, but not erased.

CD-RW and DVD-RW

CD-ReWritable (CD-RW) and DVD-ReWritable (DVD-RW) discs, unlike CD-Rs and DVD-Rs, can have data burnt onto them and also erased so that the discs can be re-used.

Flash Memory

Flash memory is a type of Electronically-Erasable Programmable Read-Only Memory (EEPROM). Flash memory is non-volatile (like ROM) but the data stored in it can also be erased or changed (like RAM).

USB Memory Sticks

Memory sticks (or ‘thumb-drives’) have made many other forms of portable storage almost obsolete (why burn a CD or DVD when you can more easily copy your files onto a memory stick?). Memory sticks are non-volatile, random-access storage devices. Each of these small devices has some flash memory connected to a USB interface.

Memory Cards

Many of our digital devices (cameras, mobile phones, MP3 players, etc.) require compact, non-volatile data storage. Flash memory cards provide this and come in a variety of shapes and sizes.

Smart Cards

Many credit cards (e.g. ‘chip-and-pin’ cards), door entry cards, satellite TV cards, etc.

FILE ALLOCATION

In allocating disk space, several issues are involved:

• When a new file is created, is the maximum space required for the file allocated at once?

• Is space allocated to a file as one or more contiguous units? We shall refer to these units as portions. That is, a portion is a contiguous set of allocated blocks.

An example of such a structure is a file allocation table (FAT), found on DOS and some other systems.

Let us examine these issues in turn.

Preallocation versus Dynamic Allocation

A pre-allocation policy requires that the maximum size of a file be declared at the time of the file creation request. In a number of cases, such as program compilations, the production of 21 summary data files, or the transfer of a file from another system over a communications network, this value can be reliably estimated.

FILE ALLOCATION METHODS

The direct-access nature of disks allows us flexibility in the implementation of files. In almost every case, files will be stored on the same disk. The main problem is how to allocate space to these files so that disk space is utilised effectively and file can be accessed quickly.

Three major methods of allocating disk space are in wide use: contiguous, linked and indexed.

Contiguous Allocation

With contiguous allocation, a single contiguous set of blocks is allocated to a file at the time of file creation.

Linked/Chained Allocation

At the opposite extreme from contiguous allocation is chained allocation. Typically, allocation is on an individual block basis. Each block contains a pointer to the next block in the chain.

Indexed Allocation

Indexed allocation addresses many of the problems of contiguous and linked/chained allocation. In this case, the file allocation table contains a separate one-level index for each file; the index has one entry for each portion allocated to the file.

SECTION FIVE

FILE PROCESSING AND APPLICATIONS

INTRODUCTION

Data could be in form of numbers, text, images, or sounds. A computer can not notice errors in the data being processed in the way that humans do. Validation checks are an attempt to build into the computer programme power of judgment so that incorrect items of data are detected and reported.

FILE PROCESSING ACTIVITIES

i. Updating: When a master file is changed to reflect a current position especially when record is added or removed. For example, updating a customer ledger record with the new one or updating a student record or score with new one.

,

ii. Referencing: When a file is accessed, it may be to ascertain what is contained there in, for example, reference can be made to a particular price file during invoicing to check if the record remains the same.

iii. File maintenance: New records must be added to a file and records need to be deleted.

iv. File enquiry or interrogation: In concept, it is similar to referencing, it involves the need to ascertain a piece of information from a master file. For example extracting, selecting or searching for a particular record from the master file.

DATA VALIDATION

In computing, data validation is the process of ensuring that a programme operates on clean, correct and appropriate data. It uses routines, often called “validation rules” or “check routines”, that check for correctness, meaningfulness, and security of data that are input to the system.

The checks can be made at two steps:

a. Input – when data is first input to the computer, different checks can be applied to prevent errors going forward for processing.

b. Update – further checking is possible when data input are matched with master files.

Validation Methods                                                PART II

• Format or picture check

Checks that the data is in a specified format (template), e.g., dates are in the format DD/MM/YYYY.

• Data type checks: Checks the data type of the input and give an error message if the input data does not match with the chosen data type, e.g. In an input box accepting numeric data, if the letter 'O' was typed instead of the number zero, or letter ‘I’ is entered instead of figure ‘1’, an error message would appear.

• Range check: Checks that the data lie within a specified range of values, e.g., the month of a person's date of birth should lie between 1 and 12.

• Limit check: Unlike range checks, data is checked for one limit only, upper OR lower, e.g., data should not be greater than 2 (>2).

• Presence check: Checks that important data are actually present and have not been missed out, e.g., customers may be required to have their telephone numbers listed.

• Check digits: Used for numerical data. An extra digit is added to a number which is calculated from the digits. The computer checks this calculation when data are entered, e.g., The ISBN (International Standard Book Number) for a book. The last digit is a check digit calculated using a modulus 11 method.

• Batch totals: Check for missing records. Numerical fields may be added together for all records in a batch. The batch total is entered and the computer checks that the total is correct, e.g., add the 'Total Cost' field of a number of transactions together.

• Hash totals: This is just a batch total done on one or more numeric fields which appears in every record, e.g., add the Telephone Numbers together for a number of Customers.

• Spelling and grammar check: Look for spelling and grammatical errors.

• Consistency Checks: Checks fields to ensure data in these fields corresponds, e.g., If Title = “Mr.”, then Gender = "M".

• Cross-system Consistency Checks: Compares data in different systems to ensure it is consistent, e.g., the address for the customer with the same id is the same in both systems.

• File existence check: Checks that a file with a specified name exists. This check is essential for programs that use file handling.

• Logic check: Checks that an input does not yield a logic error, e.g., an input value should not be 0 when there will be a number that divides it somewhere in a programme.

Data Dictionary

Data Dictionary, in computer science, is the description of the data stored in a database. The content of the data dictionary may best be thought of as “data about the data”—that is, description of all of the other objects (files, programs, and so on) in the system.

Data Corruption

Data corruption refers to errors in computer data that occur during transmission or retrieval, introducing unintended changes to the original data.

Causes of Data loss

Data loss during storage has two broad causes: hardware and software failure. Head crashes, and general wear and tear of media fall into the former category, while software failure typically occurs due to bugs in the code.

FILE MANAGERS

File Manager

A file manager or file browser is a computer program that provides a user interface to work with file systems. The most common operations are create, open, edit, view, print, play, rename, move, copy, delete, attributes, properties, search/find, and permissions.

i. File-List File Manager

Less well-known, but older are the so-called file-list file managers.

Examples include flist which was in use since 1981 on the Conversational Monitor System. This is a variant of fulist which originated before late 1978 according to comments by its author Theo Alkema.

ii. Navigational File Manager

A navigational file manager, also called an Explorer type manager, is a newer type of file manager which became prominent because of its integration in Microsoft Windows. The Windows Explorer is a classic representative of the type, using a "navigational" metaphor to represent file system locations.

Features of Navigational File Manager

• The window displays the location currently being viewed.

• The location being viewed (the current directory) can be changed by the user, by opening folders, pressing a back button, typing a location, or using additional pane with the navigation tree representing part or all the file system.

• Icons represent files, programs, and directories.

Example of Navigational File Manager

Notable examples include:

• Windows Explorer

• Mac OS X Finder

• XTree / ZTreeWin

• XYplorer

Web-Based File Manager

Web-based file managers are typically scripts written in PHP, Perl, Asp or any other server side languages. When installed on a local server or on a remotely hosted server they allow files and folders located there to be managed and edited without the need for FTP Access.

MANAGING FILES IN WINDOWS

There are as many file managers in the software market. In this unit, we learn how to manage files in Microsoft Windows Operating System. Also discussed are some useful tips for a successful management of electronic files.

Management Files in Windows

There are three ways of managing files in Windows operating systems:

• From within a Programme

• By using My Computer and

• By using Windows Explorer.

a. Managing Files from within a Programme

When you choose “File”  “Save As” from within a programme such as Microsoft Word, a dialogue box appears with three important features:

• “Save in” (near the top of the box)

A dropdown box that brings up your computer’s directory structure, to allow you to choose where to save your file.

• “File name” (near the bottom of the box)

Allows you to type in a name for your file.

• “Save as type” (at the bottom of the box)

A dropdown box that allows you to choose a format (type) for your file. The default file format will appear with the default file extension.

b. Using My Computer

Double-clicking on the My Computer icon, which is located in the upper left-hand corner of your desktop, will open a window labelled My Computer.

• At the “top” level of the directory structure are the drives, differentiated by letters:

• A:\ is your floppy disk drive

• C:\ is your hard disk

• D:\ is your Zip, CD, or DVD drive

• F:\ is probably your flash

• Go to “View” at the top of the window to change the way files and folders are displayed

within the window. There are four ways to view files and folders:

Large icons

Small icons

List – Choose this when you want to work with several files or folders at a time.

Details – This is a good mode to work in when you want to see when the file was created, its size, and other important information.

• Up – Choosing “Up” enables you to navigate through the computer’s directory structure quickly. Clicking on this button will change the contents of the current window, taking you “up” in the directory structure until you get to the highest level, at which only the drives are shown.

• Cut – • Copy – • Paste – • Undo –• Delete –

• Properties – Choosing “Properties” will bring up a box that gives you information about a particular file or folder.

Using Windows Explore

• In Windows Explorer, the entire directory structure is always available at all times in the left-hand pane. In this respect it differs from My Computer.

• Another difference between Windows Explorer and My Computer is that Windows

Explorer allows you to drag-and-drop files and folders with the mouse.

• In the left-hand pane, drives, directories, and subdirectories are visible.

To expand your view of the contents of a drive or directory, click on the + sign next to the directory name.

To collapse your view of the contents of a drive or directory, click on the – sign next to the directory name.

My Documents Dialog Box

Sorting Files

You can sort files in My Computer and Windows Explorer by clicking once on the Name, Size, Type, or Modified header buttons.

Working with More than One File

To select two or more separate files, hold down the “Ctrl” key and click on each filename. To select a contiguous group of files in a list, click on the first filename, then hold down the “Shift”  key and click on the last filename.

LOCATING LOST FILE

Use the “Find File” facility of your operating system by going to “Start” ”Find” ”Files or Folders.”

Tips for Management of Electronic Files

It is very important to keep the files on your computer organized and up to-date. Just as with paper files, the goal of computer file management is to ensure that you can find what you’re looking for, even if you’re looking for.

• Organise by file types. Make applications easier to find by creating a folder called Program Files on your drive and keeping all your applications there. For instance, the executables for Word, PowerPoint, Simply Accounting and WinZip would all reside in the Program Files folder.

• One place for all. Place all documents in the My Documents folder and nowhere else. So whether it’s a spreadsheet, a letter or a PowerPoint presentation, it goes here.

• Create folders in My Documents. These are the drawers of your computer’s filing cabinet, so to speak

• Nest folders within folders. Create other folders within these main folders as need arises.

• Follow the file naming conventions. Do not use spaces in file names, keep file names under 27 characters, and use all lower case. So a file named for a place should be noun Abuja rather than Noun Abuja. If you break any of these rules, be consistent about it.

FILE SORTING, SEARCHING, AND MERGING

Computer or electronic files are stored in main memory or secondary storage devices. We may need to retrieve, arrange or manipulate these files for some purposes.

Sorting and Search Algorithms

Different types of algorithms abound in the literature with regards to file sorting, searching, processing and so on. Below is a discussion on two of the popular operations on file handling.

Sorting Algorithm

In computer science and mathematics, a sorting algorithm is a prescribed set of well-defined rules or instructions that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. More formally, the output must satisfy two conditions:

1. The output is in non-decreasing order (each element is no smaller than the previous element according to the desired total order);

2. The output is a permutation, or reordering, of the input. Since the dawn of computing, the sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement.  Summaries of Popular Sorting Algorithms are as follows:

• Bubble Sort: This is a sorting algorithm that continuously steps through a list, swapping items until they appear in the correct order. The algorithm starts at the beginning of the data set.

• Insertion Sort: This is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list.

• Merge Sort: Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second.

• Quick Sort: Quick sort is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time and in-place.

SECTION FIVE

FILE SYSTEM PERFORMANCE AND RELIABILITY

INTRODUCTION

It is very essential that a file system is reliable, long-lasting and perform optimally.

File System Performance

Access to disk is much slower than access to memory. Reading a memory word typically takes a few hundred nanoseconds at most. Reading a disk block takes tens of milliseconds, a factor of 100,000slower. As a result of this difference in access time, many file systems have been designed to reduce the number of disk accesses needed.

Methods of Improving Performance

a. Block Caching

The most common technique used to reduce disk accesses is the block cache or buffer cache. (Cache is pronounced “cash,” and is derived from the French cacher, meaning to hide.) In this context, a cache is a collection of blocks that logically belong on the disk, but are being kept in memory for performance reasons.

b. Reduction in Disk Motion

Caching is not the only way to increase the performance of a file system.

Another important technique is to reduce the amount of disk arm motion by putting blocks that are likely to be accessed in sequence close to each other, preferably in the same cylinder.

File System Reliability

Destruction of a file system is often a far greater disaster than destruction of a computer.

Techniques to Improve Reliability

a. Bad Block Management

Two solutions to the bad block problems are used, one hardware and the other software.

• The hardware solution is to dedicate a sector on the disk to the bad block list.

• Software solution requires the user or file system to carefully construct a file containing all the bad blocks.

b. Backups

Even with a clever strategy for dealing with bad blocks, it is important to back up files frequently.

• Full dump simply refers to making a backup copy of the whole disk on another disk or machine.

File System Consistency

Another way of safeguarding data is to check for file consistency. The directory information in the main memory is more updated than that residing on the disk

FILE SYSTEM SECURITY AND INTEGRITY

File systems often contain information that is highly valuable to their users.

The Security Environment

Security has many facets. Two of the more important ones relate to data loss and intrusion. Some of the common causes of data loss are:

• Natural phenomenon such as: fire, flood, earthquakes, wars, riots or attacks from rodents

• Hardware or software errors: CPU malfunctions, unreadable disks or tapes, telecommunication errors, program bugs

• Human errors: incorrect data entry, wrong tape or disk mounted, wrong program run, lost disk or tape.

Most of these can be dealt with by maintaining adequate backups, preferably far away from the original data.

System Protection

To protect the system, we must take security measures at four levels:

• Physical: The site or sites containing the computer systems must be physically secured against armed or surreptitious entry by intruders.

• Human: Users must be screened carefully to reduce the chances of authorising a user who then gives access to an intruder (in exchange for a bribe, for example).

• Network: Much computer data in modern systems travels over private leased lines, shared lines such as: the Internet, or dial-up lines.

• Operating system: The system must protect itself from accidental or purposeful security breaches.

Security at the first two levels must be maintained if operating-system security is to be ensured.

User Authentication

A major security problem for operating systems is authentication. The protection system depends on the ability to identify the programs and processes currently executing, which in turn depends on the ability to identify each user of the system. The process of identifying users when they log on is called user authentication. Generally, authentication is based on one or more of three items:

• User possession (a key or card)

• User knowledge (a user identifier and password)

• User attributes (fingerprint, retina pattern, or signature).

Passwords

The most common approach to authenticating a user identity is the use of passwords. When a user identifies herself by user ID or account name, she is asked for a password. If the user-supplied password matches the password stored in the system, the system assumes that the user is legitimate.

Biometrics

There are many other variations to the use of passwords for authentication. Palmor hand-readers are commonly used to secure physical access—for example, access to a data center. These readers match stored parameters against what is being read from hand-reader pads. The parameters can include a temperature map, as well as finger

length, finger width, and line patterns. These devices are currently too large and expensive to be used for normal computer authentication.

Programme Threats

When a program written by one user may be used by another, misuse and unexpected behavior may result. Some common methods by which users gain access to the programs of others are:

• Trojan horses

• Trap doors

• Stack and buffer overflow.

Trojan Horse

Many systems have mechanisms for allowing programs written by users to be executed by other users. If these programs are executed in a domain that provides the access rights of the executing user, the other users may misuse these rights. A text-editor program, for example, may include code to search the file to be edited for certain keywords. If any are found, the entire file may be copied to a special area accessible to the creator of the text editor. A code segment that misuses its environment is called a Trojan horse.

Trap Door

The designer of a program or system might leave a hole in the software that only he/she is capable of using. This type of security breach is called trap door.

Stack and Buffer Overflow

This is the most common way for an attacker outside of the system, on a network or dial-up connection, to gain unauthorized access to the target system.

System Threats

Most operating systems provide a means by which processes can spawn other processes. In such an environment, it is possible to create a situation where operating system resources and user files are misused.

The two most common methods for achieving this misuse are worms and viruses. We discuss each below, along with a somewhat different form of system threat: denial of service.

Worms

A worm is a process that uses the spawn mechanism to ravage system performance. The worm spawns copies of itself, using up system resources and perhaps locking out all other processes. On computer networks, worms are particularly potent, since they may reproduce themselves among systems and thus shut down the entire network.

Viruses

Like worms, viruses are designed to spread into other programmes and can wreck havoc in a system by modifying or destroying files and causing system crashes and programme malfunctions. Whereas a worm is structured as a complete, standalone programme, a virus is a fragment of code embedded in a legitimate programme. Viruses are a major problem for computer users, especially users of microcomputer systems.

sources or disk exchange is the safest route to preventing infection. For macro viruses, one defense is to exchange Word documents in an alternative file format called rich text format (RTF). Unlike the native Word format, RTF does not include the capability to attach macros. Another defense is to avoid opening any e-mail attachments from unknown users.

FILE PROTECTION

There are three most popular implementations of file protection:

• File Naming :It depends upon the inability of a user to access a file he cannot name.

This can be implemented by allowing only users to see the files they have created.

• Password Protection: This scheme associates a password to each file. If a user does not know the password associated to a file then he cannot access it.

• Access Control: An access list is associated with each file or directory. The access list contains information on the type of users and accesses that they can do on a directory or file. An example is the following access list associated to a UNIX file or directory:

drwxrwxrwx

The d indicates that this is an access list for a directory, the first rwx indicates that it can be read, written, and executed by the owner of the file, the second rwx is an access information for users belonging to the same group as the owner (somewhere on the system is a list of users belonging to same group as the owner), and the last rwx for all other users.