ECCS-4221: Operating Systems
Credit :4-3-3-0
Instructor : Lt .Measho Berhe
Fall: 2025
ECCS-4221: Operating Systems
Chapters 6: Mass-Storage
Structure and File System
• Mass-Storage Systems
• Disk Structure
• Disk Attachment
• Disk Scheduling
• Disk Management
• Swap-Space Management
• RAID Structure
• I/O Systems
• I/O Hardware
• Application I/O Interface
• Kernel I/O Subsystem
• Transforming I/O Requests to Hardware Operations
Lecture Outline • Streams
• File Systems
• File Concept
• Access Methods
• Directory and Disk Structures
• File Sharing
• File-System Structure
• File-System Implementation
• Directory Implementation
• Allocation Methods
• Free-Space Management
• Recovery
• Network File System (NFS)
• By the end of this chapter, students will be able to:
• Mass-Storage Systems
• Describe the structure and organization of disk drives.
• Explain different disk attachment methods and their roles in system performance.
• Apply disk scheduling algorithms and compare their effectiveness.
• Discuss disk management techniques, including formatting, booting, and bad-block handling.
• Explain swap-space management and its impact on memory performance.
• Understand RAID structures, levels, and their trade-offs in reliability and performance.
• I/O Systems
• Describe the components and functions of I/O hardware.
• Explain the application I/O interface and how user programs interact with devices.
• Discuss the role of the kernel I/O subsystem, including buffering, caching, and spooling.
• Describe how I/O requests are transformed into hardware operations.
Learning Objectives
• Understand the concept of streams and their use in I/O communication.
• File Systems
• Explain the file concept and the logical structure of files.
• Compare different file access methods and their use cases.
• Describe directory structures and disk organizations used in file systems.
• Discuss mechanisms for file sharing and protection.
• Understand the logical and physical structure of file systems.
• Describe file-system implementation methods, including metadata management.
• Compare different directory implementation techniques.
• Evaluate allocation methods (contiguous, linked, indexed) and their advantages.
• Explain free-space management techniques.
• Understand file-system recovery strategies and consistency mechanisms.
• Describe the Network File System (NFS) and its architecture.
Mass Storage Structure
• Bulk of secondary storage for modern Moving-Head Disk Mechanism
computers is hard disk drives (HDDs) and
nonvolatile memory (NVM) devices
• HDDs spin platters of magnetically-coated
material under moving read-write heads
• Drives rotate at 60 to 250 times per second
• Transfer rate is rate at which data flow between
drive and computer
• Positioning time (random-access time) is time to
move disk arm to desired cylinder (seek time) and
time for desired sector to rotate under the disk
head (rotational latency)
• Head crash results from disk head making
contact with the disk surface -- That’s bad
• Disks can be removable
5
Hard Disk Drives
• Platters range(diameters) from .85” to 14” (historically)
• Commonly 3.5”, 2.5”, and 1.8”
• Range from 30GB to 3TB per drive
• Performance
• Transfer Rate – theoretical – 6 Gb/sec
• Effective Transfer Rate – real – 1Gb/sec
• Seek time from 3ms to 12ms – 9ms common for desktop
drives
• Average seek time measured or calculated based on 1/3 of
tracks
• Latency based on spindle speed
• 1 / (RPM / 60)= 60 / RPM
• 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑙𝑎𝑡𝑒𝑛𝑐𝑦 = ½ 𝑙𝑎𝑡𝑒𝑛𝑐𝑦
6
Hard Disk Performance
• 𝑨𝒄𝒄𝒆𝒔𝒔 𝑳𝒂𝒕𝒆𝒏𝒄𝒚 = 𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒂𝒄𝒄𝒆𝒔𝒔 𝒕𝒊𝒎𝒆 = 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑠𝑒𝑒𝑘 𝑡𝑖𝑚𝑒 + 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑙𝑎𝑡𝑒𝑛𝑐𝑦
• For fastest disk 3𝑚𝑠 + 2𝑚𝑠 = 5𝑚𝑠
• For slow disk 9𝑚𝑠 + 5.56𝑚𝑠 = 14.56𝑚𝑠
• 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝐼/𝑂 𝑡𝑖𝑚𝑒 = 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 𝑎𝑐𝑐𝑒𝑠𝑠 𝑡𝑖𝑚𝑒 + (𝑎𝑚𝑜𝑢𝑛𝑡 𝑡𝑜 𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟 / 𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟 𝑟𝑎𝑡𝑒) + 𝑐𝑜𝑛𝑡𝑟𝑜𝑙𝑙𝑒𝑟 𝑜𝑣𝑒𝑟ℎ𝑒𝑎𝑑
• For example, to transfer a 4KB block on a 7200 RPM disk with a 5ms
average seek time, 1Gb/sec transfer rate with a .1ms controller overhead =
• 5𝑚𝑠 + 4.17𝑚𝑠 + 0.1𝑚𝑠 + 𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟 𝑡𝑖𝑚𝑒
4K×8b 32𝐾𝑏 32𝑥1024𝑏𝑠 32𝑠
• 𝑇𝑟𝑎𝑛𝑠𝑓𝑒𝑟 𝑇𝑖𝑚𝑒 = = = = = 0.031 𝑚𝑠
1Gb/s 1𝐺𝑏/𝑠 1024𝑥1024𝑥1024 1024𝑥1024
𝑙𝑎𝑡𝑒𝑛𝑐𝑦 60
• 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑙𝑎𝑡𝑒𝑛𝑐𝑦 = = = 4.17𝑚𝑠
2 2𝑥7200
• 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝐼/𝑂 𝑡𝑖𝑚𝑒 𝑓𝑜𝑟 4𝐾𝐵 𝑏𝑙𝑜𝑐𝑘 = 9.27𝑚𝑠 + .031𝑚𝑠 = 9.301𝑚𝑠
7
Nonvolatile Memory Devices
• Solid-State Drives (SSDs) are a type of storage device • Have characteristics that present challenges
that uses NAND-based flash memory to store data. • Read and written in “page” increments (think sector) but can’t
• Unlike traditional Hard Disk Drives (HDDs), which use overwrite in place
spinning magnetic disks and mechanical read/write • Must first be erased, and erases happen in larger ”block”
heads, SSDs have no moving parts increments
• Can only be erased a limited number of times before worn
• Other forms include USB drives (thumb drive, flash out – ~ 100,000
drive), DRAM disk replacements, surface-mounted on • Life span measured in drive writes per day (DWPD)
motherboards, and main storage in devices like • A 1TB NAND drive with rating of 5DWPD is expected
smartphones to have 5TB per day written within warrantee period
without failing
• Can be more reliable than HDDs
• More expensive per MB
• Maybe have shorter life span – need careful
management
• Less capacity
• But much faster
• Busses can be too slow -> connect directly to PCI for
example
• No moving parts, so no seek time or rotational latency
8
Disk Attachment
• Host-attached storage accessed through I/O ports talking to I/O busses
• Several busses available, including advanced technology attachment (ATA), serial ATA (SATA), eSATA,
serial attached SCSI (SAS), universal serial bus (USB), and fibre channel (FC).
• Most common is SATA
• Because NVM much faster than HDD, new fast interface for NVM called NVM express (NVMe),
connecting directly to PCI bus
• Data transfers on a bus carried out by special electronic processors called controllers (or host-bus
adapters, HBAs)
• Host controller on the computer end of the bus, device controller on device end
• Computer places command on host controller, using memory-mapped I/O ports
• Host controller sends messages to device controller
• Data transferred via DMA between device and computer DRAM
10
HDD Scheduling
• The operating system is responsible for using hardware efficiently — for the
disk drives, this means having a fast access time and disk bandwidth
• Minimize seek time
• Seek time seek distance
• Disk bandwidth is the total number of bytes transferred, divided by the total
time between the first request for service and the completion of the last
transfer
• There are many sources of disk I/O request
• OS
• System processes
• Users processes
• I/O request includes input or output mode, disk address, memory address,
number of sectors to transfer
• OS maintains queue of requests, per disk or device
• Idle disk can immediately work on I/O request, busy disk means work must
queue
• Optimization algorithms only make sense when a queue exists
11
Disk Scheduling (Cont.)
• Note that drive controllers have small buffers and can manage a queue
of I/O requests (of varying “depth”)
• Several algorithms exist to schedule the servicing of disk I/O requests
• The analysis is true for one or many platters
• We illustrate scheduling algorithms with a request queue (0-199)
98, 183, 37, 122, 14, 124, 65, 67
Head pointer 53
12
FCFS(First-Come, First-Served)
• Requests are serviced in the exact order they arrive in the queue.
• The head moves from its current position to the first request in the queue, then to the next, and so on.
• No reordering of requests is done to optimize seek time.
• It can result in large total head movement and is the simplest algorithm to implement.
• Total head movement is calculated by summing the absolute differences between consecutive cylinder
accesses, starting from the initial head position.
Illustration shows total head movement of 640 cylinders
Abs
Destination Source
(Destination-Source)
98 53 45
183 98 85
37 183 146
122 37 85
14 122 108
124 14 110
124 65 59
67 65 2
Total Movements 640
13
SCAN
• The disk arm starts at one end of the disk, and moves toward the other end,
servicing requests until it gets to the other end of the disk, where the head
movement is reversed and servicing continues.
• SCAN algorithm Sometimes called the elevator algorithm
• Illustration shows total head movement of 236 cylinders
• But note that if requests are uniformly dense, largest density at another end of
disk and those wait the longest
Abs
Destination Source (Destination-Source)
53 37 16
37 14 23
14 0 14
0 65 65
65 67 2
67 122 55
122 124 2
124 183 59
Total Movements 236
14
C-SCAN
• Provides a more uniform wait time than SCAN
• The head moves from one end of the disk to the other, servicing requests as it
goes
• When it reaches the other end, however, it immediately returns to the beginning of the
disk, without servicing any requests on the return trip
• Treats the cylinders as a circular list that wraps around from the last cylinder to
the first one
• Total number of cylinders?
Abs
Destination Source
(Destination-Source)
53 65 12
65 67 2
67 98 31
98 122 24
122 124 2
124 183 59
183 199 16
199 0 199
0 14 14
14 37 23
Total Movements 382
15
Swap-Space Management
• Used for moving entire processes (swapping), or pages (paging), from
DRAM to secondary storage when DRAM not large enough for all
processes
• Operating system provides swap space management
• Secondary storage slower than DRAM, so important to optimize performance
• Usually multiple swap spaces possible – decreasing I/O load on any given device
• Best to have dedicated devices
• Can be in raw partition or a file within a file system (for convenience of adding)
• Data structures for swapping on Linux systems:
16
Storage Attachment
• Computers access storage in three ways
• host-attached
• network-attached
• cloud
• Host attached access through local I/O ports, using one of several
technologies
• To attach many devices, use storage busses such as USB, firewire, thunderbolt
• High-end systems use fibre channel (FC)
• High-speed serial architecture using fibre or copper cables
• Multiple hosts and storage devices can connect to the FC fabric
17
Network-Attached Storage
• Network-attached storage (NAS) is storage made available over a network
rather than over a local connection (such as a bus)
• Remotely attaching to file systems
• NFS and CIFS are common protocols
• Implemented via remote procedure calls (RPCs) between host and storage
over typically TCP or UDP on IP network
• Internet Small Computer System Interface(iSCSI)protocol uses IP network to
carry the SCSI protocol
• Remotely attaching to devices (blocks)
18
Cloud Storage
• Similar to NAS, provides access to storage across a network
• Unlike NAS, accessed over the Internet or a WAN to remote data center
• NAS presented as just another file system, while cloud storage is API
based, with programs using the APIs to provide access
• Examples include Dropbox, Amazon S3, Microsoft OneDrive, Apple iCloud
• Use APIs because of latency and failure scenarios (NAS protocols wouldn’t work
well)
19
RAID Structure
• RAID is a storage technique that combines multiple physical disks into one logical unit to improve
• performance,
• reliability (fault tolerance), or both.
• RAID – redundant array of inexpensive disks
• multiple disk drives provides reliability via redundancy
• Increases the mean time to failure(MTTF)
• Mean time to repair (MTTR)– exposure time when another failure could cause data loss
• Mean time to data loss(MTTDL) based on above factors
MTTF2
• 𝑀𝑇𝑇𝐷𝐿 = 2xMTTR
• Suppose that the failures of the two drives are independent.
• If mirrored disks fail independently, consider disk with 100,000 mean time to failure and 10 hour mean time to
repair
100, 0002
• Mean time to data loss is 2x100 = 500x106 hours, or 57,000 years!
• Frequently combined with NVRAM to improve write performance
• Several improvements in disk-use techniques involve the use of multiple disks working cooperatively
20
RAID (Cont.)
• Disk striping uses a group of disks as one storage unit
• Data striping consists of splitting the bits of each byte across multiple drives;
such striping is called bit-level striping
• RAID is arranged into six different levels
• RAID schemes improve performance and improve the reliability of the storage
system by storing redundant data
• Mirroring or shadowing (RAID 1) keeps duplicate of each disk
• Striped mirrors (RAID 1+0) or mirrored stripes (RAID 0+1) provides high performance and
high reliability(see slide number 21)
• Block interleaved parity (RAID 4, 5, 6) uses much less redundancy
• RAID within a storage array can still fail if the array fails, so automatic
replication of the data between arrays is common
• Frequently, a small number of hot-spare disks are left unallocated,
automatically replacing a failed disk and having data rebuilt onto them
21
RAID Levels
RAID (0 + 1) and (1 + 0)
22
File Concept
• Contiguous logical address space
• Types:
• Data
• Numeric
• Character
• Binary
• Program
• Contents defined by file’s creator
• Many types
• text file,
• source file,
• executable file
23
File Attributes
• Name – only information kept in human-readable form
• Identifier – unique tag (number) identifies file within file system
• Type – needed for systems that support different types
• Location – pointer to file location on device
• Size – current file size
• Protection – controls who can do reading, writing, executing
• Time, date, and user identification – data for protection, security, and
usage monitoring
• Information about files are kept in the directory structure, which is
maintained on the disk
• Many variations, including extended file attributes such as file checksum
• Information kept in the directory structure
24
File Operations
• Create
• Write – at write pointer location
• Read – at read pointer location
• Reposition within file - seek
• Delete
• Truncate
• Open (Fi) – search the directory structure on
disk for entry Fi, and move the content of entry
to memory
• Close (Fi) – move the content of entry Fi in
memory to directory structure on disk
25
Open Files
• Several pieces of data are needed to
manage open files:
• Open-file table: tracks open files
• File pointer: pointer to last read/write location,
per process that has the file open
• File-open count: counter of number of times a
file is open – to allow removal of data from open-
file table when last processes closes it
• Disk location of the file: cache of data access
information
• Access rights: per-process access mode
information
26
File Locking
• Provided by some operating systems and file
systems
• Similar to reader-writer locks
• Shared lock similar to reader lock – several
processes can acquire concurrently
• Exclusive lock similar to writer lock
• Mediates access to a file
• Mandatory or advisory:
• Mandatory – access is denied depending on
locks held and requested
• Advisory – processes can find status of locks
and decide what to do
27
File Types – Name, Extension
28
File Structure
• None - sequence of words, bytes
• Simple record structure
• Lines
• Fixed length
• Variable length
• Complex Structures
• Formatted document
• Relocatable load file
• Can simulate last two with first method by
inserting appropriate control characters
• Who decides:
• Operating system
• Program
29
Access Methods
• A file is fixed length logical records
• Sequential Access
• Direct Access
• Other Access Methods
Sequential Access Direct Access
• Operations • Operations
• read next • read n
• write n
• write next
• position to n
• Reset • read next
• no read after last write (rewrite) • write next
• rewrite n
• Figure n = relative block number
• Relative block numbers allow OS to
decide where file should be placed
30
Simulation of Sequential Access on Direct-access File
Other Access Methods
• Can be other access methods built on top of base methods
• General involve creation of an index for the file
• Keep index in memory for fast determination of location of data to be operated on
(consider Universal Produce Code (UPC code) plus record of data about that item)
• If the index is too large, create an in-memory index, which an index of a disk index
• IBM indexed sequential-access method (ISAM)
• Small master index, points to disk blocks of secondary index
• File kept sorted on a defined key
• All done by the OS
31
Disk Structure
• Disk can be subdivided into partitions
• Disks or partitions can be RAID protected against failure
• Disk or partition can be used raw – without a file system, or formatted with a file system
• Partitions also known as minidisks, slices
• Entity containing file system is known as a volume
• Each volume containing a file system also tracks that file system’s info in device directory or volume
table of contents
• In addition to general-purpose file systems there are many special-purpose file systems, frequently
all within the same operating system or computer
A Typical File-system Organization
32
Types of File Systems
• We mostly talk of general-purpose file systems
• But systems frequently have may file systems, some general- and some
special- purpose
• Consider Solaris has
• tmpfs – memory-based volatile FS for fast, temporary I/O
• objfs – interface into kernel memory to get kernel symbols for debugging
• ctfs – contract file system for managing daemons
• lofs – loopback file system allows one FS to be accessed in place of another
• procfs – kernel interface to process structures
• ufs, zfs – general purpose file systems
• Windows
• NTFS (New Technology File System)
• FAT32 (File Allocation Table 32)
33
Directory Structure
• A collection of nodes containing information about all files
• Both the directory structure and the files reside on disk
34
Operations Performed on Directory
• Search for a file
• Create a file
• Delete a file
• List a directory
• Rename a file
• Traverse the file system
35
Directory Organization
• The directory is organized logically to obtain
• Efficiency – locating a file quickly
• Naming – convenient to users
• Two users can have same name for different files
• The same file can have several different names
• Grouping – logical grouping of files by properties,
• (e.g., all Java programs, all games, …)
36
Single-Level Directory
• A single directory for all users
• Naming problem
• Grouping problem
37
Two-Level Directory
• Separate directory for each user
▪ Path name
▪ Can have the same file name for different user
▪ Efficient searching
▪ No grouping capability
38
Tree-Structured Directories
39
Current Directory
• Can designate one of the directories as the current (working) directory
• cd /spell/mail/prog
• type list
• Creating and deleting a file is done in current directory
• Example of creating a new file
• If in current directory is /mail
• The command
mkdir <dir-name>
• Results in:
• Deleting “mail” deleting the entire subtree rooted by “mail”
40
Protection
• File owner/creator should be able to control:
• What can be done
• By whom
• Types of access
• Read
• Write
• Execute
• Append
• Delete
• List
41
Access Lists and Groups in Unix
• Mode of access: read, write, execute
• Three classes of users on Unix / Linux
RWX
a) owner access 7 111
RWX
b) group access 6 110
RWX
c) public access 1 001
42
A Sample UNIX Directory Listing
ls -l
• The first field describes the protection
of the file or directory.
• A d as the first character indicates a
subdirectory.
• Also shown are the number of links to
the file,
• the owner’s name,
• the group’s name,
• the size of the file in bytes,
• the date of last modification, and
• finally, the file’s name (with optional
extension).
Question 1: Assume a user named 'DEC' in a Unix/Linux operating system created a file named [Link]. The user then
executed the command: chmod 754 [Link]. Identify which users have read, write, and execute privileges for the file
[Link]
43
Windows 7 Access-Control List Management
44