Recall: I/O Performance (Network Example)
Length (x)
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Copyright By PowCoder代写加微信 assignmentchef
Recall:A Few Queuing Theory Results
• Assumptions:
– System in equilibrium; No limit to the queue
– Time between successive arrivals is random and memoryless Ser
Arrival Rate Service Rate e λ μ=1/Tser r
• Parameters that describe our system:
Why does response/queueing delay grow unboundedly even though the utilization is < 1 ?300 200 100Response Time (ms)Throughput (Utilization) (% total BW)– Tser: – C:mean number of arriving customers/second mean time to service a customer (“m1”) squared coefficient of variance = σ2/m12– μ: service rate = 1/Tser– u: server utilization (0≤u≤1): u = λ/μ = λ × Tser • Parameters we wish to compute:– Tq: Time spent in queue– Lq: Length of queue = λ × Tq (by Little’s law) • Results:– Memoryless service distribution (C = 1): (an “M/M/1 queue”): » Tq = Tser x u/(1 – u)– General service distribution (no restrictions), 1 server (an “M/G/1 queue”): » Tq = Tser x 1⁄2(1+C) x u/(1 – u)Joseph & Kubiatowicz CS162 © UCB Spring 2022Recall:When is Disk Performance Highest?• When there are big sequential reads, or• When there is so much work to do that they can be piggy backed (reordering queues—one moment)• OK to be inefficient when things are mostly idle• Bursts are both a threat and an opportunity•
• Other techniques:
– Reduce overhead through user level drivers
– Reduce the impact of I/O delays by doing other useful work in the meantime
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Disk Scheduling (1/3)
• Disk can do only one request at a time;What order do you choose to do queued requests?
User Requests
• FIFO Order
– Fair among requesters, but order of arrival may be
to random spots on the disk ⇒Very long seeks • SSTF: Shortest seek time first
– Pick the request that’s closest on the disk
– Although called SSTF, today must include
rotational delay in calculation, since
rotation can be as long as seek
– Con: SSTF good at reducing seeks, but
may lead to starvation
Joseph & Kubiatowicz CS162 © UCB Spring 2022
2,3 2,1 3,10 7,2 5,2 2,2
Disk Scheduling (2/3)
• Disk can do only one request at a time;What order do you choose to do queued requests?
User Requests
• SCAN: Implements an Elevator Algorithm: take the closest request in the direction of travel
– No starvation, but retains flavor of SSTF
Joseph & Kubiatowicz CS162 © UCB Spring 2022
2,3 2,1 3,10 7,2 5,2 2,2
Disk Scheduling (3/3)
• Disk can do only one request at a time;What order do you choose to do queued requests?
User Requests
• C-SCAN: Circular-Scan: only goes in one direction
– Skips any requests on the way back
– Fairer than SCAN, not biased towards pages in middle
Joseph & Kubiatowicz CS162 © UCB Spring 2022
2,3 2,1 3,10 7,2 5,2 2,2
Recall: How do we Hide I/O Latency?
• Blocking Interface: “Wait”
– When request data (e.g., read() system call), put process to sleep until data
– When write data (e.g., write() system call), put process to sleep until device is ready for data
• Non-blocking Interface: “Don’t Wait”
– Returns quickly from read or write request with count of bytes successfully
transferred to kernel
– Read may return nothing, write may write nothing
• Asynchronous Interface: “Tell Me Later”
– When requesting data, take pointer to user’s buffer, return immediately; later
kernel fills buffer and notifies user
– When sending data, take pointer to user’s buffer, return immediately; later kernel takes data and notifies user
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: I/O and Storage Layers
Application / Service
File System
File Descriptors
open(), read(), write(), close(), … Open File Descriptions
High Level I/O
Low Level I/O
Files/Directories/Indexes
I/O Driver
Commands and Data Transfers Disks, Flash, Controllers, DMA
What we covered in Lecture 4
What we will cover next…
What we just covered…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
From Storage to File Systems
I/O API and syscalls
File System
Variable-Size Buffer
Memory Address
Logical Index, Typically 4 KB
Physical Index, 512B or 4KB
Sector(s) Sector(s)
Flash Trans. Layer
Phys. Block
Erasure Page
Hardware Devices
Phys Index., 4KB
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Building a File System
• File System: Layer of OS that transforms block interface of disks (or other block devices) into Files, Directories, etc.
• Classic OS situation:Take limited hardware interface (array of blocks) and provide a more convenient/useful interface with:
– Naming: Find file by name, not block numbers – Organize file names with directories
– Organization: Map files to blocks
– Protection: Enforce access restrictions
– Reliability: Keep files intact despite crashes, hardware failures, etc.
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: User vs. System View of a File
• User’s view:
– Durable Data Structures
• System’s view (system call interface):
– Collection of Bytes (UNIX)
– Doesn’t matter to system what kind of data structures you want to store on disk!
• System’s view (inside OS):
– Collection of blocks (a block is a logical transfer unit, while a sector is the physical transfer unit)
– Block size ≥ sector size; in UNIX, block size is 4KB
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.11
Translation from User to System View
File Syste
• What happens if user says:“give me bytes 2 – 12?” – Fetch block corresponding to those bytes
– Return just the correct portion of the block
• What about writing bytes 2 – 12?
– Fetch block, modify relevant portion, write out block
• Everything inside file system is in terms of whole-size blocks – Actual disk I/O happens in blocks
– read/write smaller than block size needs to translate and buffer
Joseph & Kubiatowicz CS162 © UCB Spring 2022
File (Bytes)
Disk Management
• Basic entities on a disk:
– File: user-visible group of blocks arranged sequentially in logical space – Directory: user-visible index mapping names to files
• The disk is accessed as linear array of sectors • How to identify a sector?
– Physical position
» Sectors is a vector [cylinder, surface, sector] » Not used anymore
» OS/BIOS must deal with bad sectors
– Logical Block Addressing (LBA)
» Every sector has integer address
» Controller translates from address ⇒ physical position »S from structure of disk
Joseph & Kubiatowicz CS162 © UCB Spring 2022
What Does the File System Need?
• Track free disk blocks
– Need to know where to put newly written data
• Track which blocks contain data for which files – Need to know where to read a file from
• Track files in a directory
– Find list of file’s blocks given its name
• Where do we maintain all of this? – Somewhere on disk
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Data Structures on Disk
• Bit different than data structures in memory
• Access a block at a time
– Can’t efficiently read/write a single word – Have to read/write full block containing it – Ideally want sequential access patterns
• Durability
– Ideally, file system is in meaningful state upon shutdown – This obviously isn’t always the case…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FILE SYSTEM DESIGN
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.16
Critical Factors in File System Design
• (Hard) Disks Performance !!!
– Maximize sequential access, minimize seeks
• Open before Read/Write
– Can perform protection checks and look up where the actual file resource are, in advance
• Size is determined as they are used !!!
– Can write (or read zeros) to expand the file – Start small and grow, need to make room
• Organized into directories
– What data structure (on disk) for that?
• Need to carefully allocate / free blocks – Such that access remains efficient
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Components of a File System
Directory Structure
File Header Structure
File number
One Block = multiple sectors Ex: 512 sector, 4K block
Data blocks
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall:Abstract Representation of a Process
Suppose that we execute open(“foo.txt”)
and that the result is 3
Next, suppose that we execute
read(3, buf, 100)
and that the result is 100
Thread’s Regs
Address Space (Memory)
User Space Kernel Space
Not shown: Initially contains 0, 1, and 2 (stdin, stdout, stderr)
Open File Description
File Descriptors 3
File: foo.txt Position: 100
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Open file description is better described as remembering the inumber (file number) of the file, not its name
Components of a File System
Thread’s Regs
Address Space (Memory)
User Space
Kernel Space
File Descriptors 3
Open File Description
File: foo.txt
Position: 100
Not shown: Initially contains 0, 1, and 2 (stdin, stdout, stderr)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Components of a File System
file name file number
offset directory structure offset index structure
storage block
• Open performs Name Resolution
– Translates path name into a “file number”
• Read and Write operate on the file number
– Use file number as an “index” to locate the blocks
• 4 components:
– directory, index structure, storage blocks, free space map
Joseph & Kubiatowicz CS162 © UCB Spring 2022
How to get the File Number?
• Look up in directory structure
• A directory is a file containing
– File number could be a file or another directory
– Operating system stores the mapping in the directory in a format it interprets – Each
• Process isn’t allowed to read the raw bytes of a directory
– The read function doesn’t work on a directory
– Instead, see readdir, which iterates over the map without revealing the raw bytes
• Why shouldn’t the OS let processes read/write the bytes of a directory?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Directories
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.23
Directory Abstraction
• Directories are specialized files – Contents: List of pairs
• System calls to access directories
– open / creat / readdir traverse the structure – mkdir / rmdir add/remove entries
– link / unlink (rm)
• libc support
– DIR * opendir (const char *dirname)
– struct dirent * readdir (DIR *dirstream)
– int readdir_r (DIR *dirstream, struct dirent *entry, struct dirent **result)
/usr/lib4.3
/usr/lib4.3/foo
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Directory Structure
• How many disk accesses to resolve “/my/book/count”?
– Read in file header for root (fixed spot on disk)
– Read in first data block for root
» Table of file name/index pairs.
» Search linearly – ok since directories typically very small
– Read in file header for “my”
– Read in first data block for “my”; search for “book”
– Read in file header for “book”
– Read in first data block for “book”; search for “count” – Read in file header for “count”
• Current working directory: Per-address-space pointer to a directory used for resolving file names
– Allows user to specify relative filename instead of absolute path (say CWD=“/my/book” can resolve “count”)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
In-Memory File System Structures
• Open syscall: find inode on disk from pathname (traversing directories) – Create “in-memory inode” in system-wide open file table
– One entry in this table no matter how many instances of the file are open
• Read/write syscalls look up in-memory inode using the file handle
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Characteristics of Files
Published in FAST 2007
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Observation #1: Most Files Are Small
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.28
Observation #2: Most Bytes are in Large Files
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.29
CASE STUDY:
FAT: FILE ALLOCATION TABLE
MS-DOS, 1977 Still widely used!
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.30
FAT (File Allocation Table)
• Assume (for now) we have a way to translate a path to
a “file number”
– i.e., a directory structure
• Disk Storage is a collection of Blocks – Just hold file data (offset o = < B,x >)
• Example: file_read 31, < 2, x >
– Index into FAT with file number
– Follow linked list to block
– Read the block from disk into memory
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 2
File number
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT (File Allocation Table)
• File is a collection of disk blocks
• FAT is linked list 1-1 with blocks
• File number is index of root of block list for the file
• File offset: block number and offset within block
• Follow list to get block number
• Unused blocks marked free – Could require scan to find – Or, could use a free list
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 2
File number
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT (File Allocation Table)
• File is a collection of disk blocks
• FAT is linked list 1-1 with blocks
• File number is index of root of block list for the file
• File offset: block number and offset within block
• Follow list to get block number
• Unused blocks marked free – Could require scan to find – Or, could use a free list
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 2
File number
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT (File Allocation Table)
• File is a collection of disk blocks
• FAT is linked list 1-1 with blocks
• File number is index of root of block list for the file
• File offset: block number and offset within block
• Follow list to get block number
• Unused blocks marked free – Could require scan to find – Or, could use a free list
• Ex: file_write(31, < 3, y >) – Grab free block
– Linking them into file
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 3
File 31, Block 2
File number
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT (File Allocation Table)
• Where is FAT stored?
– On disk 0:
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 3
File 31, Block 2
• How to format a disk?
– Zero the blocks, mark FAT entries “free”
• How to quick format a disk? –AT entries “free”
• Simple: can implement in device
firmware free
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT: Directories
• A directory is a file containing
• Free space for new/deleted entries
• In FAT: file attributes are kept in directory (!!!) – Not directly associated with the file itself
• Each directory a linked list of entries
– Requires linear search of directory to find particular entry
• Where do you find root directory (“/”)?
– At well-defined place on disk
– For FAT, this is at block 2 (there are no blocks 0 or 1) – Remaining directories
Joseph & Kubiatowicz CS162 © UCB Spring 2022
FAT Discussion
Suppose you start with the file number: • Time to find block?
• Block layout for file?
• Sequential access?
• Random access? • Fragmentation? • Small files?
• Big files?
Disk Blocks
File 31, Block 0
File 31, Block 1
File 31, Block 3
File 31, Block 2
Joseph & Kubiatowicz CS162 © UCB Spring 2022
CASE STUDY:
UNIX FILE SYSTEM (BERKELEY FFS)
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.38
Inodes in Unix (Including Berkeley FFS)
• File Number is index into set of inode arrays • Index structure is an array of inodes
– File Number (inumber) is an index into the array of inodes – Each inode corresponds to a file and contains its metadata
» So, things like read/write permissions are stored with file, not in directory » Allows multiple names (directory entries) for a file
• Inode maintains a multi-level tree structure to find storage blocks for files – Great for little and large files
– Asymmetric tree with fixed sized blocks
• Original inode format appeared in BSD 4.1 (more following) – Berkeley Standard Distribution Unix!
– Part of your heritage!
– Similar structure for Linux Ext 2/3
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.39
Inode Structure
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.40
File Atributes
9 basic access control bits
– UGO x RWX SetUID bit
– execute at owner permissions rather than user
SetGID bit
– execute at group’s permissions
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.41
Small Files: 12 Pointers Direct to Data Blocks
Direct pointers
4kB blocks ⇒ sufficient for files up to 48KB
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 22.42
Large Files: 1-, 2-, 3-level indirect pointers
Indirect pointers
– point to a disk block
containing only pointers – 4 kB blocks => 1024 ptrs
=> 4 MB @ level 2 => 4 GB @ level 3 => 4 TB @ level 4
48 KB +4 MB
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Putting it All Together: On-Disk Index
• Sample file in multilevel indexed format:
– 10 direct ptrs, 1K blocks
– How many accesses for block #23? (assume file header accessed on open)?
» Two: One for indirect block, one for data
– How about block #5? » One: One for data
– Block #340?
» Three: double indirect block, indirect block, and data
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Critical Factors in File System Design
• (Hard) Disk Performance !!!
– Maximize sequential access, minimize seeks
• Open before Read/Write
– Can perform protection checks and look up where the actual file resource are, in advance
• Size is determined as they are used !!!
– Can write (or read zeros) to expand the file – Start small and grow, need to make room
• Organized into directories
– What data structure (on disk) for that?
• Need to carefully allocate / free blocks – Such that access remains efficient
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Magnetic Disks
• Cylinders: all the tracks under the head at a given point on all surfaces
Track Sector
• Read/write data is a three-stage process:
– Seek time: position the head/arm over the proper track
– Rotational latency: wait for desired sector to rotate u
程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.