Transcript File Systems, I/O and Disks

I/O, Disks and File Systems
Lecture 5, April 10, 2003
Mr. Greg Vogl
Operating Systems
Uganda Martyrs University
Overview
1. Input/Output system
–
Devices, objectives, structure, implementation
2. Disks
–
Media, structure, operations, I/O scheduling
3. Files and directories
–
Attributes, types, access, names, paths
4. File system implementation
–
Clusters, volumes, aliases
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
2
Sources
• Ritchie ch. 8-10
• Burgess 5.3-5.4, Solomon: Disks, File Systems
– Contact lecturer for help copying these to your disk
• Linux Admin. Made Easy, Frampton, ch. 4
– You may want to download free resources from the
MScIS electronic library
– Many are <1.5 MB, can fit on a floppy disk
– A 700MB CD-RW disc is only Ushs 5000
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
3
1. Input/Output Devices
• Slower than processor, memory, filesystem
• Not consistent; each device is different
– speed, transfer unit, operations, error conditions
• Use address, data and control buses
• Each device is assigned an address
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
4
How I/O Works with Processor
• Interrupts
– I/O devices can work while processor busy
– Interrupt processor when task finished
• Direct Memory Access
– Processor only starts data transfer
– Direct data transfer device  memory
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
5
Objectives of I/O System
• Efficiency
– Devices should work at maximum speed
– Don’t make processor or memory wait
• Generality and device independence
– Hide complexity from user, programmer
– Provide means of easily adding new devices
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
6
Top-down structure of I/O system
• Application program
– System calls
• I/O control system IOCS (operating system)
• Device driver (operating system)
– I/O bus
• Device controller (hardware)
• Device (hardware)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
7
Device Drivers
•
•
•
•
Translate user’s logical request to physical
Added on when device is installed
DOS allows dynamically adding drivers
UNIX requires linking with kernel
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
8
Types of Devices
• Block devices
– Transfer data in groups of characters
– Random access, bidirectional flow, error checks
– Secondary storage (e.g. magnetic tape, disks)
• Character devices
– Transfer data one character at a time
– Simpler, fewer services from OS
– Most other devices
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
9
Virtual Devices
• OS simulates a hardware device
• Responds to system calls like a real device
– E.g. print spooler behaves like a real printer
Reduces app. contact with slow devices
Apps use more devices than actually present
Device independence
Transparent to user and application
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
10
Buffering
• Disk drive  OS buffer  user process
• Intermediate storage in main memory
– Frees processor to do other things
– Processing and disk transfer in parallel
• Double-buffering uses two buffers
– One is emptied while the other is filled
• Multiple buffers put in circular queue
– Pointers to buffers being filled, emptied
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
11
UNIX and Linux Input/Output
• All devices and files treated identically
– All data transfers are treated as byte streams
• /dev holds special files for devices, e.g.:
– console: system console, lp: line printer
– hdaX, hdbX: hard disk a and b partitions X=0-9
– ttyXX, ptyXX: user or pseudo terminals
• /etc/termcap file holds terminal config. info.
– null: inputs end of file, outputs discarded
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
12
DOS Input/Output
• Accessed through system calls
• ROM Basic Input-Output System (BIOS)
– Firmware built into ROM on Intel-based PCs
– Manages low-level I/O operations
• DOS services
– DOS object code loaded into memory IO.SYS
– Manages higher-level I/O services (IOCS)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
13
DOS Devices:
•
•
•
•
•
•
•
con:
com1,2:
lpt1,2,3:
prn:
A,B:
C:
D:, E:
April 10, 2003
console (keyboard/screen)
serial ports (modem)
parallel ports (printers)
logical printer port (usually lpt1:)
floppy (diskette) drives
hard disk drive
additional disk drives or partitions
Operating Systems: I/O, Disks
and File Systems
14
DOS Device Drivers
• Dynamically loaded during boot (start-up)
• Must be in a .com file with .sys extension
• config.sys is read by DOS at startup
–
–
–
–
driver=drivername.sys
e.g. mouse.sys, display.sys
himem.sys manages DOS extended memory
Other config. commands: files, buffers, country
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
15
Windows Device Drivers
•
•
•
•
•
Dynamic link libraries (DLL files)
Shareable code used by many applications
Device drivers do not affect Windows code
Software/hardware vendors create DLLs
Plug and Play automates device installation
– Devices, BIOS and OS must use PNP standard
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
16
2. Secondary Storage Media
• Magnetic media
– Hard drive
• Most common and important type of disk
• Several metal disk platters, sealed, constant spin rate
– Floppy disk
• Plastic disk, low speed and capacity, exposed to air
– Tape drives
• Similar to cassettes, sequential access, for backups
• Optical media includes CD, DVD
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
17
Hard Disk Structure
• Platters (~4-8), surfaces (~8-16)
– Each platter is 2-sided, has 2 read/write heads
• Seek time (~10ms average)
– Arm moves heads to disk track (centre/edge)
• Rotation speed (~10Krpm), latency (~5ms)
– Disks spin to sector containing start of data
• Transfer time, rate (~30 MB/sec)
– Data is transferred to/from disk (read/write)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
18
Disk Physical Locations
cylinder
platters
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
19
Disk Formatting
• Low-level formatting by manufacturer
– Sectors are smallest unit of physical storage
– usually 29 = 512 bytes
– Sectors per track can vary (less near centre)
• High-level formatting by OS (file system)
– Clusters: allocation units of 2n sectors, n~5
– FAT16/32 is used by DOS/Win9x/Linux
– FAT12 by floppies, NTFS by WinNT/2000/XP
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
20
Disk Partitioning
• Partition
– Divide disk into sections, act like separate disks
• Common uses of Partitions
– Separate OS, application software, and data
– Different OS in each partition
• Partitioning software
– fdisk (DOS/Windows and UNIX)
– Displays, adds or removes partitions
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
21
Disk Compression
• Disks can store in compressed format
• Different compression algorithms
– Use short codes for long data repetitions
• Different amounts of compression (~0-50%)
• Tradeoff: speed vs. space
Danger of losing info. increases
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
22
Disk and File System Checking
• Checksum or CRC used in each sector
• Bad sectors are labelled, avoided
– When too many bad sectors, must replace disk
• Software to check/fix hard and floppy disks:
– DOS chkdsk, Windows scandisk, UNIX fsck
– Check: allocation unit size, used/free space
– Fix: marks bad sectors, frees lost chains
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
23
Disk Fragmentation
•
•
•
•
•
Parts of files scattered all over the disk
Caused by deleting and creating files often
Disk heads move more; slows performance
Apps run slower if their parts are scattered
Defragmentation software can help
– Reduce fragmentation of disks and files
– Speed up applications
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
24
Disk Caching
• Memory copies of recently used disk blocks
• Write cached blocks to disk when file closes
• The cache has limited size, will become full
– Flush to disk blocks that are least recently used
– Similar to virtual memory algorithms
• If computer loses power, memory is erased
– Periodically flush cache in case of power loss
– In UNIX, user can type sync, then shutdown
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
25
RAM Disk
• Simulate a disk by using memory
• DOS/Win98 assigns a volume drive letter
Acts very much like a real disk
Allows using files and folders
Performance is much faster than a real disk
Memory is more expensive than disk
Memory is smaller than most disks
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
26
Disk I/O Scheduling
• Goals
– High transfer rate yet fairness to many requests
– Minimise wear on mechanical parts of disk
• Algorithms
–
–
–
–
First come first served
Shortest seek time first
Scan or elevator/lift
Circular scan or one way elevator
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
27
First Come First Served
• Each disk access is first-come-first-serve
Appropriate for single-process systems
Disk may thrash among multiple user requests
• First user uses disk until file access finished
Simplest; better performance than above
Disk requests may still be scattered all over
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
28
Shortest Seek Time First
• Service request at closest head position
Best overall performance
Not fair; requests can starve
Heads may still reverse direction
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
29
Scan or Elevator/Lift
• Only move disk head one direction at a time
• Move toward next request
• When reaching one end of disk, reverse
Usually fairer than SSTF
Inner/outer edges get half as much use
Can still lead to starvation
if same cylinder keeps getting new requests
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
30
Circular Scan/One Way Elevator
• Only seek in one direction (centreedge)
• Return to centre before seeking again
One long seek increases total seek time
May be insignificant on heavily loaded disk
• Also no need to scan areas without requests
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
31
3. Files
• A file is a logical unit of user/program info.
• Files kept in “permanent” secondary storage
• Files can be of almost any length
– User doesn’t need to worry about block size
• Files can be named for easier reference
– Files can be grouped by storing in folders
• Many files per disk, per user
– Files can be protected with access rights
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
32
File Attributes (Information)
•
•
•
•
•
•
•
Filename (to uniquely identify the file)
File type (to indicate its structure or use)
File location on disk (for OS use)
Ownership, access rights (who, how)
File size in bytes (current, limit, used, on disk)
Date/Time stamps (created, accessed, changed)
Other (hidden, system, read-only, archive)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
33
File Types
• File types may be enforced/supported/used by
– the operating system (e.g. executables, folders)
– certain programs (e.g. Java compiler, Word)
– convention (or not at all!)
• File types may be indicated by
– name and/or extension
– information outside the file (e.g. directory)
– its contents (e.g. first two bytes of UNIX file)
• UNIX and DOS let apps manage file types
– A file is treated as unstructured stream of bytes
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
34
Some Ways to Classify Files
• Text (ASCII)
– Plain text (human languages e.g. readme files)
– Source files (programming language code)
– Markup language (e.g. HTML)
• Database
– Records file (array of records, fixed or variable length)
– Index file (maps keysvalues)
• Binary
– Executable (machine code language)
– Data/App. (graphics, sound, Word, Excel)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
35
Ways to Access Files
• Sequential
– read/write next record or n bytes; rewind
– Often used for sequential media e.g. tape
• Random
– read/write nth record or bytes i-j; seek
• Indexed
– read/write record with given key
– Often used for indexed (database) files
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
36
UNIX File Types
• Regular: program, text, data
– First 2 bytes indicate if file is executable
•
•
•
•
Directory: contains references to other files
Special file: character or block (for I/O)
Pipe: a buffer for process communication
ls -l displays file attributes:
– Regular, directory, character or block file
– read/write/execute access by user/group/other
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
37
DOS File Names
• 8 character name + 3 character extension
• Extensions used by DOS and applications
• Some special symbols used for other things
–
–
–
–
–
\ directories
: devices including disks
/ command options or switches
? * wildcards (one or many characters)
<>| redirection
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
38
DOS File Attributes
•
•
•
•
System: operating system files
Archive: used by file backup programs
Hidden: not visible to user
Read-only: cannot be changed or deleted
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
39
Windows File Names
• long name + extension (1 to 255 characters)
• Can contain spaces
– Enclose in double quotes when using in DOS
• Alias for compatibility with DOS file name
– uses first six characters plus ~1, ~2
• Many extensions associated w/ applications
– .txt Notepad, .doc Word, .xls Excel, etc.
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
40
UNIX File Names
•
•
•
•
<=14 characters on old systems, 255 on new
Names are case sensitive (A not same as a)
Most characters are allowed (but not space)
A few special characters unused in names
– / directories, ?* wildcards, <>| redirection
• Extensions sometimes used by convention
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
41
Directories or Folders
• Contains references to files, other folders
• Directory commands (DOS and/or UNIX)
– dir, ls, cd, pwd, mkdir, md, rmdir, rd
• Current or working directory (.)
– Directory where a shell or process is working
– cd or pwd displays working directory of shell
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
42
Paths
• Most modern file systems are hierarchical
–
–
–
–
Directories can contain other directories
Root directory (\ or /) is at top (bottom of tree)
All other directories are below/inside the root
Parent directory (..) is one level “up”
• Relative vs. absolute paths to a file
– Relative paths start from working directory
– Absolute (full) paths names start from root
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
43
Search Path
• A list of folders separated by semicolons (;)
– e.g. path=c:\windows;c:\windows\command
• Used by shell/process to find files/programs
– First search in current directory
– Then in each folder listed in the search path
• Path can be set upon startup or by the user
– PATH command in DOS and UNIX shells
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
44
4. Clusters
• Each file uses at least one full cluster
• Tradeoffs of large cluster sizes
Fewer disk accesses; better performance
Few FAT entries: take less space, fast to search
Small files waste most of the cluster
• Floppies use only one sector per cluster
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
45
Cluster Management Schemes
• Clusters of one file can be anywhere on disk
• Chain
– Each cluster holds number of next cluster
Part of cluster space wasted for pointer
Only serial access is possible
• Cluster list
– Directory stores list of clusters for each file
Variable length lists are difficult to manage
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
46
DOS File Allocation Table (FAT)
• Table of 16-bit values, each 0000 to FFFF
– 1st FAT entry identifies disk type
– 2nd FAT entry is always FFFF
• One FAT entry per cluster
– Each FAT entry number = cluster number
• FAT entries are chained together
– 0000 = free cluster, FFFF = end of a chain
• FAT is copied into memory for fast access
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
47
DOS Volume Structure
• Boot sector
– Disk and allocation details, bootstrap loader etc.
• FAT
– Plus duplicate (backup) FATs
• Root directory
– Fixed size, originally a maximum of 112 entries
• File space
– Rest of disk is used for files, up to the disk size
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
48
Windows Shortcuts
• Shortcut: a file pointing to another file/app
• Accessing the shortcut opens the file/app
• Right-click a shortcut to view its properties
– Target = file pointed to, Start in = working dir
– Shortcut key, run maximised/minimised, etc.
• Useful places to find or put shortcuts
– Menus: Start, Programs, Favourites, Documents
– Desktop, QuickLaunch toolbar
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
49
Windows NT File System
• Security and reliability
– Recovery, bad sector repair, parity disk striping
• Large file sizes
– 64-bit file space, up to 264 bytes
• Unicode file names
– 16-bit characters for international symbols
• Some POSIX (portable UNIX) compliance
– Case sensitive file names, hard links (aliases)
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
50
UNIX Inodes
• Directory stores only
– file names, inode pointers
• Inode stores
– owner, group, permissions, date/time stamps
– file size, file type
– number of links to the file (reference count)
• When reference count is 0, file is removed
– 13 pointers to data and index blocks
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
51
UNIX Inode Pointers
• First 10 pointers are direct (data blocks)
• Last 3 pointers are indirect
– 11th points to index block of pointers to data
– 12th points to index of indexes
– 13th points to index of index of indexes
Provides direct access for small files <5K
Allows storage of very large files
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
52
UNIX Links
• A UNIX file can have more than one name
– breaks hierarchical structure
• A link can be created to any existing file
– programs use link() system call; users type ln
• Soft link (created by ln -s)
– Deleting all soft links to file deletes the file
• Hard link (created by ln)
– Deleting any hard link deletes the file
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
53
Mounting
• How can one computer use multiple disks?
• Windows has separate tree per disk/partition
• UNIX has only one tree
–
–
–
–
–
Attach additional disks to a directory in /dev
Mount each device to a mount point
Directory becomes alias for root folder of disk
Used for hard and floppy disks, tape drives, etc.
Use NFS to mount disks on remote computers
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
54
UNIX Volume Structure
• Boot block
– First stage boot program, loads system loader
• Super block
– Disk size, allocation of inodes and data blocks
• Inodes
– Storage space for inodes (fixed but expandable)
• Data blocks
– Blocks for files and directories
April 10, 2003
Operating Systems: I/O, Disks
and File Systems
55