[SOLVED] CS CS162 UCB Spring 2022

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

Copyright By Assignmentchef 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 (0u1): u = / = Tser Parameters we wish to compute: Tq: Time spent in queue Lq: Length of queue = Tq (by Littles 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 12(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 queuesone 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 thats 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: Dont 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 users buffer, return immediately; later
kernel fills buffer and notifies user
When sending data, take pointer to users 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
Users view:
Durable Data Structures
Systems view (system call interface):
Collection of Bytes (UNIX)
Doesnt matter to system what kind of data structures you want to store on disk!
Systems 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 files 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
Cant 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 isnt 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
Threads 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
Threads 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 isnt allowed to read the raw bytes of a directory
The read function doesnt work on a directory
Instead, see readdir, which iterates over the map without revealing the raw bytes
Why shouldnt 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 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

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 groups 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]