Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    MODULE CO4

    Uploaded by

    ishorishore

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MODULE CO4

    Uploaded by

    ishorishore
    2 views13 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views13 pages

    MODULE CO4

    Uploaded by

    ishorishore

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 13

    MODULE IV

    File organization and disk scheduling algorithms

    M4.01 Define the concept of file system & file operations


    Concept of file and directory
    File
    • File is a collection of records related to each other.
    • A file is a named collection of related information that is recorded on
    secondary storage such as magnetic disks, magnetic tapes and optical disks.
    Three types of files structure in OS:

    • A text files
    • An object files
    • A source files

    File Attributes
    It stores meta information like file creation date and time, current size, last
    modified date, etc. All this information is called the attributes of a file
    system.

    File attributes:

    • Name
    • Identifier
    • Location
    • Type
    • Size
    • Protection
    • Time, date and security
    Directory
    • The collection of files is a file directory.
    • The directory contains information about the files, including attributes,
    location, and ownership.
    Various file operations
    • A file is a collection of logically related data that is recorded on the
    secondary storage in the form of sequence of operations.
    • The various operations which can be implemented on a file such as read,
    write, open and close etc. are called file operations.

    1.Create: This operation is used to create a new file in the file system

    2.Open: Once the file is created, it must be opened before performing the file
    processing operations.

    3. Write: This operation is used to write the information into a file.

    4. Read: This operation reads the contents from a file.

    5. Delete: A file is removed from the existing file structure.

    6.close: When the processing of the file is complete, it should be closed.

    7.Append: This operation adds data to the end of the file.

    8. Rename: This operation is used to rename the existing file.

    M4.02 Explain different file organizations


    • File organization refers to the way data is stored in a file
    Type of file organization
    1.Sequential file organization
    • A sequential file is one in which the individual records can only be
    accessed sequentially.
    • New records are always added to the end of the file.
    • A sequential file contains records organized by the order in which they
    were entered.
    • The order of the records is fixed.
    • Records in sequential files can be read or written only sequentially.
    • After you place a record into a sequential file, you cannot shorten,
    lengthen, or delete the record.

    Indexed file organization


    • An indexed file is a file in which each record includes a primary key.
    • The primary key must be unique for each record.
    • Records can then be accessed randomly by specifying the value of primary
    key. Indexed file records can also be accessed sequentially.
    • An index is built for every file
    • The Index is searched sequentially, and its pointer can access the file
    directly.
    • Multiple levels of indexing can be used to offer greater efficiency in access.
    • It also reduces the time needed to access a single record.

    M4.03 Classify directory structures


    • A directory structure is the way an operating system arranges files that are
    accessible to the user.
    • A directory is a container that is used to contain folders and files.
    • It organizes files and folders in a hierarchical manner.

    Directory structure can be classified in to three types,


    1.Single-Level Directory
    • Simple to implement, but each file must have a unique name.
    • The single-level directory is the simplest directory structure.
    • All files are contained in the same directory which makes it easy to support
    and understand.
    • A single level directory files are in the same directory; they must have
    a unique name.

    2. Two-level directory:
    • Here creates a separate directory for each user.
    • In the two-level directory structure, each user has their own user files
    directory (UFD).
    • The UFDs have similar structures, but each list only the files of a single
    user. System’s master file directory (MFD) is searched whenever a new
    user id is correct.

    3. Tree Structure/ Hierarchical Structure:

    • Tree directory structure of operating system is most commonly used in


    our personal computers.
    • User can create both files and subdirectories.
    • This directory structure is tree like structure, where the root directory is at
    the peak.
    • The root contains all the directories for each user.
    • The users can create subdirectories and even store files in their directory.
    • A user does not have access to the root directory data and cannot modify it.
    • The user does not have access to other user’s directories.

    M4.04 Illustrate file allocation methods


    File Allocation method
    The allocation methods define how the files are stored in the disk blocks
    Three types of space allocation methods are:

    • Contiguous Allocation
    • Linked Allocation
    • Indexed Allocation

    Contiguous Allocation
    Contiguous Allocation allocate each file in a contiguous set of blocks on the disk.

    • Every file user a contiguous address space on memory.


    • Here, the OS assigns disk address is in linear order.
    • Here external fragmentation is occurred.

    Advantage

    • Easy to implement
    • Excellent read performance

    Disadvantage

    • Disk will become fragmented


    • Difficult to grow file.
    Linked Allocation
    In this method,

    • Every file includes a list of links.


    • Noncontiguous memory allocation
    • The directory contains a link or pointer in the first block of a file.
    • With this method, there is no external fragmentation
    • This File allocation method is used for sequential access files.
    • This method is not ideal for a direct access file.

    Advantage

    • No external fragmentation
    • File size can increase

    Disadvantage

    • Large seek time


    • Direct access difficult
    • Overhead of pointer.

    Indexed Allocation
    In this method,
    • Indexed allocation have a special block is called index block.
    • An index block contains the pointer to all the blocks occupied by a file.
    • Directory contains the addresses of index blocks of the specific files.
    • Each file has its own index block.

    Advantage

    • No external fragmentation
    • Support direct access

    Disadvantage

    • Multilevel index
    • Overhead of pointer

    M4.05 Explain disk scheduling algorithms.


    • Disk scheduling is done by operating systems to schedule I/O requests
    arriving for the disk.
    • Disk scheduling is also known as I/O Scheduling.
    • It used for reduce the total seek time.
    • Disk Scheduling Algorithms
    1. FCFS (First Come First Serve)
    2. SSTF (Shortest Seek Time First)
    3. SCAN (Elevator Algorithm)
    4. C-SCAN (Circular SCAN)
    5. LOOK
    6. C-LOOK

    Seek time: The time it takes for the read/write head to find the data on the disk.
    Latency time: The time it takes for the sector containing the data to rotate into position under the head.

    1.FCFS disk scheduling algorithm


    • FCFS is the simplest of all Disk Scheduling Algorithms.
    • In FCFS, the requests are addressed in the order they arrive in the
    disk queue.

    Example: The order of request is- (82,170,43,140,24,16,190)


    And current position of disk head is: 50
    Total disk head movement (Seek time) =
    (82-50) +(170-82) +(170-43) +(140-43) +(140-24) +(24-16) + (190-16)
    =642
    Advantage
    • It is simple to implement.
    • It improves response time.
    Disadvantage
    • Throughput is not efficient.
    • It is used in small system where I/O efficiency is not
    important.
    • It involves lot of random head movement.

    2.SSTF disk scheduling algorithm

    • SSTF stands for Shortest Seek Time First is a disk scheduling algorithm.

    • In SSTF the tracks that are closer to the current disk head position
    should be serviced first in order to minimize the seek operations is
    basically known as Shortest Seek Time First (SSTF).
    • It provides better throughput.
    • This algorithm is used in Batch Processing systems.
    • It has a less average response and waiting time.
    E.g.: Here gives an array of track number is 98,37,14,124,65,67 and
    initial head position is 32.
    Advantage
    • It minimizes the latency time
    • Better through than FCFS
    Disadvantage
    • Starvation may occur.
    • It is not optimal

    3.SCAN Disk Scheduling Algorithm


    • This algorithm is simple and easy to understand.
    • It is also called as Elevator Algorithm.
    • In the SCAN Disk Scheduling Algorithm, the head starts from one end
    of the disk and moves towards the other end, servicing requests in
    between one by one and reaching the other end.
    • The direction of the head is reversed and the process continues as the
    head continuously scans back and forth to access the disk.
    • this algorithm works as an elevator and is hence also known as
    the elevator algorithm.
    • The requests at the midrange are serviced more and those arriving
    behind the disk arm will have to wait.
    Advantage
    ▪ Simple easy to understand
    ▪ Low variance in response and waiting time

    Eg The order of request:12,34,52,14,25,68,39


    The Initial head position:53
    Direction towards: large tracks
    Total number of tracks:90

    4.C-SCAN algorithm
    • It is circular SCAN algorithm.
    • The (C-SCAN) Scheduling Algorithm is a modified version of the SCAN Disk Scheduling
    Algorithm
    • Like SCAN (Elevator Algorithm), C-SCAN moves the head from one end servicing all
    the requests to the other end.
    • Then it immediately returns to the beginning of the disk without
    servicing any requests on the return trip and starts servicing again once
    reaches the beginning.
    • In this algorithm, the direction must be considered, that is, towards larger or
    smaller value.
    • This algorithm moves towards the end of disk requests and serves them.
    Advantage
    • It provides better response time
    • It provides uniform waiting time.
    Dis advantage
    • May not be fair to service requests for tracks at the extreme end.
    • It has more seek movements as compared to the SCAN Algorithm.

    The LOOK Disk Scheduling Algorithm

    • The LOOK Disk Scheduling Algorithm is the advanced version of the


    SCAN (elevator) disk scheduling algorithm
    • It gives slightly better seek time than any other algorithm.
    • The LOOK algorithm operates by scanning the disk in a specific direction.
    • In LOOK scheduling the arm goes only as far as final request in each
    direction.
    • Then it reverses direction immediately with out going all the way to the
    end of the disk.
    • This algorithm the head is not allowed to move till the end of the disk.
    Advantage
    o Better the SCAN algorithm in terms of head movement
    Disadvantage
    • Doesn’t provide uniform waiting time.
    Eg. Request sequence:12,34,52,14,25,68,39
    Read/write head:53
    Total number of tracks:90
    Direction towards: large tracks

    C-LOOK Disk Scheduling Algorithm

    • C-LOOK Disk Scheduling Algorithm is an enhanced version of


    both SCAN as well as LOOK disk scheduling algorithms.
    • Determine the initial position of the disk head.
    • Sort the pending disk requests in the order in which they will be
    serviced.
    • Scan the disk in the chosen direction, servicing requests as they are
    encountered.
    • When the last request in the current direction has been serviced,
    immediately return to the beginning of the disk and repeat the
    process.
    Advantage
    • Low variance in waiting time and response time.
    Disadvantage
    • More overhead to finding end request.

    Eg. Request sequence:12,34,52,14,25,68,39


    Read/write head:53
    Total number of tracks:90
    Direction towards: large tracks

    You might also like