Transcript Here - SIUE Computer Science - Southern Illinois University

CS 314 Operating Systems
File System
Department of Computer Science
Southern Illinois University Edwardsville
Spring, 2016
Dr. Hiroshi Fujinoki
E-mail: [email protected]
File_System/001
CS 314 Operating Systems
What is “file system”?
File system is an OS component that manages files for users (or applications)
Hide implementation
Device
Drivers
• Logical Structure
• Semantics
Semantics &
Logical Structure
Users
e.g., “Read 100 bytes from “my.txt”
File
System
CD-ROM
Drive Unit
Device
Drivers
Software implementation
of files and directories
Hard-Disk
Drive Unit
(Hardware)
• Software implementation of files and directories
• Hide implementations details (absorb various types in hardware device)
• Provide users with high-level manipulations for files
File_System/002
CS 314 Operating Systems
Why do we need file system (or files)?
Question: Why not just memory (why do we need “files”)?
 Information must survive after a system is shut down
 Capacity of physical memory is usually limited
Paging
(We can’t perform big application)
 IPC through memory (shared memory) is not easy
IPC through a file (pipe) is easier
 Identifying data you want to access is easy
• You can give a file name to a set of data
• You don’t have to use a pointer to access data
(OS (i.e., file system) does this for you)
 Manipulating set of data is easy in file
- save - copy - concatenate - delete - move
File_System/003
CS 314 Operating Systems
The five essential functions in a file system
Regular files: a unit of data to be manipulated
 Storing files
Directories: A special file that gives a tree-like
hierarchical structure to ordinary files
 Free-disk space management (bit-map, array, linked-list)
Similar to “free-memory management”
 Disk space allocation for each file (FAT, i-node, etc)
 User interface (let human users manipulate files)
create, read, write, append, copy, move, etc.
 Access control (Who can read, write, execute, delete a file?)
File_System/004
CS 314 Operating Systems
Categories of files
For saving
your data
Files for which unit
of I/O is “character”
Ordinary Files
Executable Files
Character Files
Regular
Files
Special Files
I/O Files
Files for which I/O
can be performed
Files
Tree Files
Ordinary Files
File_System/005
For saving
your data
Block Files
Files for which unit
of I/O is “record”
Directories
As the interface
to an I/O device
Special Files
As the interface
to an I/O device
CS 314 Operating Systems
Hierarchical Directory Systems
= File (ordinary file)
• Files are a leaf-node (user data will be stored there)
• Directories can have
files and/or directories
= Directory
Root Directory
CD (Change Directory)
• Each drive (file system)
starts with the root directory
CD (Change Directory)
CWD (Current Working Directory)
• Directories can be a leaf-node
• Ownership of a directory is
usually inherited to child
directories
Most of modern OSes use HDS
File_System/006
CS 314 Operating Systems
Executable Files
Program codes
(machine codes)
CPU
Executable File
File
Header
Program
Codes
   
File_System/007
Data &
Constants
Relocation
bits
Symbol
Table
 Magic Number
 Entry point
 Program code size
 Flags
 Data size
 BSS size
 Symbol table size
CS 314 Operating Systems
Internal File Organizations
How does the contents in a file looks from user’s view?
 Character Sequence (A.K.A “Byte Sequence”)
file
- You request data from file. The file system returns the requested
data as a sequence of bytes.
- No structure in returned data
record
(OS does not care the contents. It’s all up to you.)
Example: read (file_ID, buffer, number_bytes);
 Block Sequence (A.K.A. “Record Sequence”)
- Contents in a file are organized as “records”
- File read/write is in the unit of “record”
Example: fprintf (name, address, phone_num, age);
file
File_System/008
“record”
CS 314 Operating Systems
Two access methods to files
1. Sequential Access
• Data in a file can be accessed from the beginning of a file to the end
• Data is accessed always in the same order
• Example: file saved on a tape
Access Head
File_System/010
CS 314 Operating Systems
Two access methods to files
2. Random Access
• Data in a file can be accessed from any where within a file
• You can specify data in a file (usually as “record”)
• Example: files saved on hard disk and floppy disk
Data
Access Head
File
Disk
File_System/011
CS 314 Operating Systems (from CS312 Computer Architecture)
Hardware Organization (Disk)
Motor spindle
(physical)
Track
(logical)
Disk-Drive Unit
Disk
(physical)
File_System/017
sector
(logical)
CS 314 Operating Systems
File System Implementation
 Sector allocations to files & managing sector allocations to files
Contiguous allocation
(a) File space allocations
Non-Contiguous allocation
Linked-list (“chained”)
(b) Managing space allocations
Indexed
File_System/018
CS 314 Operating Systems (from CS312 Computer Architecture)
File System Implementation
 Structure of a file system
Physical Drive Capacity
File_System/012
Disk (Disk Platter)
CS 314 Operating Systems
Logical internal format of a disk drive
 Structure of a file system
Physical Drive Capacity
MBR
Partition
Table
Partition #1
Logical Drive
  
Partition #N
Logical Drive
• Size of a partition
• The first sector for a partition
• The last sector for a partition
• Type of file system used for this partition
File_System/013
CS 314 Operating Systems
File System Implementation
 Structure of a file system
Physical Drive Capacity
MBR
Partition
Table
Partition #1
  
Partition #N
Logical Drive
Boot Super Free Space File Allocation The Root
Block Block Management Information Directory
Logical Drive
File_System/014
Other files &
directories
CS 314 Operating Systems
System Boot Sequence
 You turn on power
 CPU jumps to the beginning of BIOS ROM
 CPU executes POST and initializes hardware
- Memory access latency, initialize video card, etc.
 CPU executes BIOS routine to load MBR
 CPU jumps to the routine in MBR
 MBR contains a routine to check the partition table
- Find out which logical drive is the system boot drive
- Load the boot block of the boot drive and CPU jumps to it
- The boot block contains a routine to start OS
File_System/015
CS 314 Operating Systems
File System Implementation
 Structure of a file system
Power-On
Physical Drive
MBR
Partition
Table
Partition #1
  
This is the file system
Partition #N
Logical Drive
Software
Boot Super Free Space File Allocation The Root
Block Block Management Information Directory
Hardware
File_System/016
Other files &
directories
Logical Drive #0 (the first logical drive)
CS 314 Operating Systems
* Microsoft calls “block” as “cluster”
File System Implementation
Block* (a collection of sectors)
(1) Contiguous sector allocations
File A
(5 blocks)
File B
(4 blocks)
File C
(12 blocks)
File D
(8 blocks)
File E
(7 blocks)
Advantages
 Easy implementation
File Name 1st block
File_System/019
File size
File A
File B
File C
0
5
9
5 blocks
4 blocks
12 blocks
File D
21
8 blocks
File E
29
7 blocks
 Fast access
Blocks (sectors) are always contiguous
Minimum head seek time
CS 314 Operating Systems
File System Implementation
(1) Contiguous sector allocations
File A
(5 blocks)
File B
(4 blocks)
File C
(12 blocks)
File D
(8 blocks)
File E
(7 blocks)
Disadvantages
 Halls of “free blocks”
Disk space will be wasted by halls
(external fragmentation)
 Compaction (de-fragmentation)
Expensive operation (for large disks)
File_System/020
CS 314 Operating Systems
File System Implementation
File_System/021
CS 314 Operating Systems
File System Implementation
(2) Non-Contiguous sector allocations
Advantages
• No external fragmentation
A file
Linked-list of disk blocks
(Windows’ approach)
Need to manage sector allocations
File Allocation Table (FAT)
(UNIX’s approach)
i-node
File_System/022
CS 314 Operating Systems
File System Implementation
File Name 1st block
File A
File_System/023
11
NULL
File size
5 blocks
A file
Linked-list of blocks
CS 314 Operating Systems
File System Implementation
File Allocation Table
A file
File Name 1st block
File A
11
File size
5 blocks
2
11
13
31
36
31
13
2
-1
31
File Allocation Table (FAT)
File_System/024
CS 314 Operating Systems
File System Implementation
i-node
A file
File Name Pointer
File A
What if a file is very large?
File size
11
13
2
36
31
5 blocks
i-node
File_System/025
If # of blocks needed is
more than i-node?
CS 314 Operating Systems
File System Implementation
i-node
i-node
Pointer
A file
File Name Pointer
File A
i-node
File size
i-node
i-node
5 blocks
i-node
Pointer
i-node
i-node
File_System/026
Pointer
Pointer
i-node
CS 314 Operating Systems
Memory-Mapped Files
Concept
Try to access files as memory
Disk Sector
(or a block of sectors)
File
Virtual Address
Space
File_System/027
Disk Drive
(HDD)
CS 314 Operating Systems
Memory-Mapped Files
Concept
(it’s an extension of “paging”)
Try to access files as memory
Disk Sector
(or a block of sectors)
Memory
Access
File
Virtual Address
Space
File_System/028
Disk Drive
(HDD)
CS 314 Operating Systems
Memory-Mapped Files
What are the motivations in doing this?
• We can access any data using a pointer
- No need for calling “read” or “write”
- No need for preparing “buffer” and buffer copies
status = read (fd, buffer, bytes_read);
if (status > 0)
destination [0] = buffer[0];
destination [0] = my_pointer;
- No need for “file descriptor”
File_System/029
CS 314 Operating Systems
Memory-Mapped Files
How can we use memory-mapped files?
 Map a file (to the virtual address space)
- OS calls file system and performs “open”
- It’s hidden from a user (or application program)
 A user (or application program) can access a file
as if it were memory access
- OS performs address boundary check
- It’s hidden from a user (or application program)
 Un-map the file
- OS saves updated data in the file
- OS calls file system and performs “close”
File_System/030
CS 314 Operating Systems
Disk Sector
(or a block of sectors)
Memory-Mapped Files
“Segmentation” can be applied to Memory-mapped files
Segment
File
0000
0000
0000
Disk Drive
(HDD)

Virtual Address
Space (Segment #2)
Virtual Address
Space (Segment #1)
File_System/031
All segments start at address = 0
Virtual Address
Space (Segment #N)
CS 314 Operating Systems
File_System/000