Operating Systems

Dr P S Patheja
Disk Scheduling
 Review: Want Standard Interfaces to Devices
• Block Devices: e.g. disk drives, tape drives, Cdrom
– Access blocks of data
– Commands include open(), read(), write(), seek()
– Raw I/O or file-system access
– Memory-mapped file access possible

Dr P S Patheja
 Review: Want Standard Interfaces to Devices
• Block Devices: e.g. disk drives, tape drives, Cdrom
– Access blocks of data
– Commands include open(), read(), write(), seek()
– Raw I/O or file-system access
– Memory-mapped file access possible
• Character Devices: e.g. keyboards, mice, serial ports,
some USB devices
– Single characters at a time
– Commands include get(), put()
– Libraries layered on top allow line editing

Dr P S Patheja
 Review: Want Standard Interfaces to Devices
• Block Devices: e.g. disk drives, tape drives, Cdrom
– Access blocks of data
– Commands include open(), read(), write(), seek()
– Raw I/O or file-system access
– Memory-mapped file access possible
• Character Devices: e.g. keyboards, mice, serial ports,
some USB devices
– Single characters at a time
– Commands include get(), put()
– Libraries layered on top allow line editing

Dr P S Patheja
• Network Devices: e.g. Ethernet, Wireless, Bluetooth
– different enough from block/character to have own interface
– Unix and Windows include socket interface
• Separates network protocol from network operation
• Includes select() functionality
– Usage: pipes, FIFOs, streams, queues, mailboxes
 Hard Disk Drives

Read/Write Head
Side View

Dr P S Patheja
Western Digital Drive
http://www.storagereview.com/guide/
IBM/Hitachi Microdrive
 Properties of a Hard Magnetic Disk
Sector

Platters

Track

• Properties
– Independently addressable element: sector
• OS always transfers groups of sectors together—”blocks”
– A disk can access directly any given block of information it
contains (random access). Can access any file either
sequentially or randomly.
– A disk can be rewritten in place: it is possible to
read/modify/write a block from the disk

Dr P S Patheja
• Typical numbers (depending on the disk size):
– 500 to more than 20,000 tracks per surface
– 32 to 800 sectors per track
• A sector is the smallest unit that can be read or written
• Zoned bit recording
– Constant bit density: more sectors on outer tracks
– Speed varies with track location
 Disk I/O Performance
Response 300
Time (ms)

Controller
User 200
Disk
Thread
Queue 100
[OS Paths]
Response Time = Queue + Disk Service Time
0 100%
0%
Throughput (Utilization)
• Performance of disk drive/file system (% total BW)
– Metrics: Response Time, Throughput
– Contributing factors to latency:
• Software paths (can be loosely modeled by a queue)

Dr P S Patheja
• Hardware controller
• Physical disk media
• Queuing behavior:
– Can lead to big increases of latency as utilization approaches
100%
 Track
Magnetic Disk Characteristic Sector
• Cylinder: all the tracks under the
head at a given point on all surface Head
• Read/write data is a three-stage Cylinder
process: Platter
– Seek time: position the head/arm over the proper track (into proper
cylinder)
– Rotational latency: wait for the desired sector to rotate under the read/write
head
– Transfer time: transfer a block of bits (sector) under the read-write head
• Disk Latency = Queueing Time + Controller time +
Seek Time + Rotation Time + Xfer Time
Controller
Software Hardware

Dr P S Patheja
Request

Result
Media Time
Queue
(Seek+Rot+Xfer)
(Device Driver)

• Highest Bandwidth:
– transfer large group of blocks sequentially from one track
 Overview of Mass Storage Structure
• Magnetic disks provide bulk of secondary storage of modern
computers
– Drives rotate at 60 to 200 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

Dr P S Patheja
• That’s bad
• Disks can be removable
• Drive attached to computer via I/O bus
– Busses vary, including EIDE, ATA, SATA, USB, Fibre Channel, SCSI
– Host controller in computer uses bus to talk to disk controller
built into drive or storage array
Moving-head Disk Mechanism
 Disk Structure
• Disk drives are addressed as large 1-dimensional
arrays of logical blocks, where the logical block
is the smallest unit of transfer.

• The 1-dimensional array of logical blocks is

mapped into the sectors of the disk sequentially.
– Sector 0 is the first sector of the first track on the
outermost cylinder.

Dr P S Patheja
– Mapping proceeds in order through that track, then
the rest of the tracks in that cylinder, and then
through the rest of the cylinders from outermost to
innermost.
 Free Space Management
• How can we keep track of free blocks of the disk?
– Which blocks are free?
• We need this info when we want to allocate a new
block to a file.
– Allocate a block that is free.
• There are several methods to keep track of free
blocks:

Dr P S Patheja
– Bit vector (bitmap) method
– Linked list method
– Grouping
– Counting
13
 Free-Space Management:
Bit Vector (Bit map)
• We have a bit vector (bitmap) where we have one bit
per block indicating if the block is used or free.
• If the block is free the corresponding bit can be 1,
else it can be 0 (or vice versa).
1: free : White Color
Example:
0: used : Blue Color
Disk Blocks 0 1 2 3 4 5 6 7 8 9 10 11

Dr P S Patheja
0000
1101
0110

BitMap
Used
free

CS342 Operating Systems İbrahim Körpeoğlu, Bilkent University 14

 Disk Attachment
• Host-attached storage accessed through I/O ports
talking to I/O busses
• SCSI itself is a bus, up to 16 devices on one cable, SCSI
initiator requests operation and SCSI targets perform
tasks
– Each target can have up to 8 logical units (disks
attached to device controller
• FC is high-speed serial architecture

Dr P S Patheja
– Can be switched fabric with 24-bit address space –
the basis of storage area networks (SANs) in which
many hosts attach to many storage units
– Can be arbitrated loop (FC-AL) of 126 devices
 Disk Scheduling
• The operating system is responsible for using hardware
efficiently — for the disk drives, this means having a fast
access time and disk bandwidth.
• Access time has two major components
– Seek time is the time for the disk are to move the heads to the
cylinder containing the desired sector.
– Rotational latency is the additional time waiting for the disk to
rotate the desired sector to the disk head.
• Minimize seek time

Dr P S Patheja
• 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.
 Disk Scheduling (Cont.)
• Several algorithms exist to schedule the
servicing of disk I/O requests.
• We illustrate them with a request queue (0-
199).

Dr P S Patheja
98, 183, 37, 122, 14, 124, 65, 67

Head pointer 53
 FCFS
Illustration shows total head movement of 640 cylinders.

45
85
146
85
108
110
59
2

45+85+146+85+108+110+59+2 = 640
 SSTF
• Selects the request with the minimum seek
time from the current head position.
• SSTF scheduling is a form of SJF scheduling;
may cause starvation of some requests.
• Illustration shows total head movement of

Dr P S Patheja
236 cylinders.
 SSTF (Cont.)

12+2+30+23+84+24+2+59 = 236 Cylinders

 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.
• Head normally starts movement towards
nearer end of the disk.

Dr P S Patheja
• Sometimes called the elevator algorithm.
• Illustration shows total head movement of
208 cylinders.
 SCAN (Cont.)

16+23+14+65+2+31+24+2+59 = 236
Look = 208
 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.

Dr P S Patheja
• Treats the cylinders as a circular list that wraps
around from the last cylinder to the first one.
 C-SCAN (Cont.)

12+2+31+24+2+59+16+14+23 = 183 / 382

 C-LOOK
• Version of C-SCAN
• Arm only goes as far as the last request
in each direction, then reverses direction
immediately, without first going all the
way to the end of the disk.

Dr P S Patheja
C-LOOK (Cont.)
 Selecting a Disk-Scheduling Algorithm
• SSTF is common and has a natural appeal
• SCAN and C-SCAN perform better for systems that
place a heavy load on the disk.
• Performance depends on the number and types of
requests.
• Requests for disk service can be influenced by the
file-allocation method.
• The disk-scheduling algorithm should be written as a

Dr P S Patheja
separate module of the operating system, allowing it
to be replaced with a different algorithm if necessary.
• Either SSTF or LOOK is a reasonable choice for the
default algorithm.
 Disk Management
• Low-level formatting, or physical formatting —
Dividing a disk into sectors that the disk controller
can read and write.
• To use a disk to hold files, the operating system still
needs to record its own data structures on the disk.
– Partition the disk into one or more groups of cylinders.
– Logical formatting or “making a file system”.
• Boot block initializes system.

Dr P S Patheja
– The bootstrap is stored in ROM.
– Bootstrap loader program.
• Methods such as sector sparing used to handle bad
blocks.
 Booting from a Disk in Windows 2000

• The MBR holds the information on how the logical partitions,

containing file systems, are organized on that medium.
• The MBR also contains executable code to function as a loader for
the installed operating system—usually by passing control over to
the loader's second stage, or in conjunction with each
partition's volume boot record (VBR).
• This MBR code is usually referred to as a boot loader.
 Swap-Space Management
• Swap-space — Virtual memory uses disk space as an
extension of main memory.
• Swap-space can be carved out of the normal file
system, or, more commonly, it can be in a separate
disk partition.
• Swap-space management
– 4.3BSD allocates swap space when process starts; holds
text segment (the program) and data segment.

Dr P S Patheja
– Kernel uses swap maps to track swap-space use.
– Solaris 2 allocates swap space only when a page is forced
out of physical memory, not when the virtual memory
page is first created.
 File-System Interface
• File Concept
• Access Methods
• Directory Structure
• File-System Mounting
• File Sharing
• Protection

Dr P S Patheja
 File Concept
• Contiguous logical address space

• Types:
– Data
• numeric
• character

Dr P S Patheja
• binary
– Program
 File Structure
• None - sequence of words, bytes
• Simple record structure
– Lines
– Fixed length
– Variable length
• Complex Structures
– Formatted document
– Relocatable load file

Dr P S Patheja
• Who decides:
– Operating system
– Program
 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,

Dr P S Patheja
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
 File Operations
• File is an abstract data type
• Create
• Write
• Read
• Reposition within file
• Delete
• Truncate

Dr P S Patheja
• 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
 Open Files
• Several pieces of data are needed to
manage 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

Dr P S Patheja
– Disk location of the file: cache of data access
information
– Access rights: per-process access mode
information
 Open File Locking
• Provided by some operating systems and file
systems
• Mediates (monitors) access to a file
• Mandatory or advisory:
– Mandatory – access is denied depending on locks
held and requested

Dr P S Patheja
– Advisory – processes can find status of locks and
decide what to do
File Types – Name, Extension
Dr P S Patheja
 File Access Methods
Sequential-access File
 Directory Structure
• A collection of nodes containing information
about all files

Directory

Files

Dr P S Patheja
F1 F2 F4
F3
Fn

Both the directory structure and the files reside on disk

Backups of these two structures are kept on tapes
Operations Performed on Directory
• Search for a file
• Create a file
• Delete a file
• List a directory
• Rename a file

Dr P S Patheja
• Traverse the file system
Organize the Directory (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

Dr P S Patheja
properties, (e.g., all Java programs, all games, …)
 Single-Level Directory
• A single directory for all users

Dr P S Patheja
Naming problem

Grouping problem
 Two-Level Directory
• Separate directory for each user

Dr P S Patheja
 Path name
 Can have the same file name for different user
 Efficient searching
 No grouping capability
Tree-Structured Directories

Dr P S Patheja
 Tree-Structured Directories (Cont)
• Efficient searching

• Grouping Capability

• Current directory (working directory)

Dr P S Patheja
– cd /spell/mail/prog
– type list
Tree-Structured Directories (Cont)
• Absolute or relative path name
• Creating a new file is done in current directory
• Delete a file
rm <file-name>
• Creating a new subdirectory is done in current
directory
mkdir <dir-name>
Example: if in current directory /mail

Dr P S Patheja
mkdir count
mail

prog copy prt exp count

Deleting “mail”  deleting the entire subtree rooted by “mail”

 Acyclic-Graph Directories
• Have shared subdirectories and files

Dr P S Patheja
 Acyclic-Graph Directories (Cont.)
• Two different names (aliasing)

• If dict deletes list  dangling pointer

Solutions:
– Backpointers, so we can delete all pointers
Variable size records a problem
– Backpointers using a daisy chain organization

Dr P S Patheja
– Entry-hold-count solution
• New directory entry type
– Link – another name (pointer) to an existing file
– Resolve the link – follow pointer to locate the file
General Graph Directory

Dr P S Patheja
 General Graph Directory (Cont.)
• How do we guarantee no cycles?
– Allow only links to file not subdirectories
– Garbage collection
– Every time a new link is added use a cycle
detection
algorithm to determine whether it is OK

Dr P S Patheja
 File Sharing
• Sharing of files on multi-user systems is
desirable
• Sharing may be done through a protection
scheme
• On distributed systems, files may be shared
across a network

Dr P S Patheja
• Network File System (NFS) is a common
distributed file-sharing method
 File Sharing – Multiple Users
• User IDs identify users, allowing
permissions and protections to be per-
user

• Group IDs allow users to be in groups,

permitting group access rights

Dr P S Patheja
 File Sharing – Remote File Systems
• Uses networking to allow file system access between systems
– Manually via programs like FTP
– Automatically, seamlessly using distributed file systems
– Semi automatically via the world wide web
• Client-server model allows clients to mount remote file systems
from servers
– Server can serve multiple clients
– Client and user-on-client identification is insecure or complicated
– NFS (Network File System) is standard UNIX client-server file
sharing protocol

Dr P S Patheja
– CIFS (Common Internet File Sys.) is standard Windows protocol
– Standard operating system file calls are translated into remote
calls
• Distributed Information Systems (distributed naming services) such
as LDAP, DNS, NIS, Active Directory implement unified access to
information needed for remote computing
 Protection
• File owner/creator should be able to control:
– what can be done
– by whom

• Types of access
– Read
– Write

Dr P S Patheja
– Execute
– Append
– Delete
– List
 Access Lists and Groups
• Mode of access: read, write, execute
• Three classes of users
RWX
a) owner access 7  111
RWX
b) group access 6  110
RWX
c) public access 1  001
• Ask manager to create a group (unique name), say G, and add
some users to the group.
• For a particular file (say game) or subdirectory, define an

Dr P S Patheja
appropriate access. owner group public

chmod 761 game

Attach a group to a file

chgrp G game
Windows XP Access-control List Management

Dr P S Patheja
A Sample UNIX Directory Listing

Dr P S Patheja
 File-System Structure
• File structure
– Logical storage unit
– Collection of related information
• File system resides on secondary storage
(disks)

Dr P S Patheja
• File system organized into layers
• File control block – storage structure
consisting of information about a file
Layered File System

Dr P S Patheja
A Typical File Control Block
 Virtual File Systems

• Virtual File Systems (VFS) provide an object-

oriented way of implementing file systems.

• VFS allows the same system call interface (the

API) to be used for different types of file

Dr P S Patheja
systems.

• The API is to the VFS interface, rather than any

specific type of file system.
Schematic View of Virtual File System
 Directory Implementation
• Linear list of file names with pointer to the data
blocks.
– simple to program
– time-consuming to execute

• Hash Table – linear list with hash data structure.

– decreases directory search time

Dr P S Patheja
– collisions – situations where two file names hash to
the same location
– fixed size
 Allocation Methods
• An allocation method refers to how disk
blocks are allocated for files:

• Contiguous allocation

Dr P S Patheja
• Linked allocation

• Indexed allocation
 Contiguous Allocation
• Each file occupies a set of contiguous blocks
on the disk
• Simple – only starting location (block #) and
length (number of blocks) are required
Drawbacks:
• Random access

Dr P S Patheja
• Wasteful of space (dynamic storage-
allocation problem)
• Files cannot grow
Contiguous Allocation of Disk Space
 Linked Allocation
• Each file is a linked list of disk blocks:
blocks may be scattered anywhere on
the disk.

block = pointer

Dr P S Patheja
Linked Allocation
 Linked Allocation (Cont.)
• Simple – need only starting address
• Free-space management system –
no waste of space
Q
• No random access LA/511
R
• Mapping
Block to be accessed is the Qth block in the

Dr P S Patheja
linked chain of blocks representing the file.
Displacement into block = R + 1
File-allocation table (FAT) – disk-space allocation
used by MS-DOS and OS/2.
File-Allocation Table
Example of Indexed Allocation
 Indexed Allocation (Cont.)
• Need index table
• Random access
• Dynamic access without external fragmentation, but
have overhead of index block.
• Mapping from logical to physical in a file of maximum
size of 256K words and block size of 512 words. We
need only 1 block for index table.
Q

Dr P S Patheja
LA/512
R
Q = displacement into index table
R = displacement into block