CS代写 CS162 © UCB Spring 2022

Recall: I/O Performance (Network Example)
Length (x)
4/6/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022

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 100 Response 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 2022 Recall: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 • – Waste space for speed?
• 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 mappings
– File number could be a file or another directory
– Operating system stores the mapping in the directory in a format it interprets – Each mapping is called a directory entry
• 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
• 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 mappings
• 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

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

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代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts