程序代写 Operating Systems – CSCI 402 – cscodehelp代写

Operating Systems – CSCI 402
Ch 6: File Systems
http://merlot.usc.edu/william/usc/
43
321 0
Copyright ý .
Operating Systems – CSCI 402
Memory
Disk Disk
44
321 0
Copyright ý . Cheng

resides on disk (or alternatives) survives software and hardware crashes
(including loss of disk?)
Quick, easy, and efficient
satisfies needs of most applications
how do applications use permanent storage?
Operating Systems – CSCI 402
Permanent storage
Requirements
45
321 0
Copyright ý . Cheng

text editors
linkers and loaders source-code control
Document processing
editing browsing
Web stuff
serving browsing
Program execution
paging
Operating Systems – CSCI 402
Software development
Applications
46
321 0
Copyright ý . Cheng

sequential is very common! “random access” is relatively rare
Operating Systems – CSCI 402
Directories
convenient naming fast lookup
File access
Needs
47
321 0
Copyright ý . Systems – CSCI 402
6.1 The Basics of File Systems
UNIX¡¯s S5FS
Disk Architecture Problems with S5FS Improving Performance
48
321 0
Copyright ý . simple file system
free space
S5FS
slow
not terribly tolerant to crashes reasonably efficient in space
no compression
Concerns
on-disk data structures
file representation
recall that AFS translates an inode number to disk address
Operating Systems – CSCI 402
49
321 0
Copyright ý . 5FS Layout
a disk block is a logical unit (usually multiple of page size) A “linear view” (1-D array of blocks) of the disk
0 1 2…
321 0
Operating Systems – CSCI 402
Boot block
Superblock
I-list
Data Region
A disk is simply an array of blocks of 1KB each (old Unix: 512B)
I-list
Data Region
50
Copyright ý . 5FS Layout
The superblock
describes the layout of the rest of the file system contains the head of the free list
The i-list is an array of index nodes (inodes) each representing a file
321 0
Operating Systems – CSCI 402
Boot block
Superblock
I-list
Data Region
where are the “free space”? inodes can be free or
not
data block can be free
or not
51
Copyright ý . 5FS: Inode
Operating Systems – CSCI 402
Device
Inode Number
Mode (File Type)
Link Count
Owner, Group
File Size
Disk Map
52
321 0
Copyright ý . Cheng

inode
Disk Map
assuming blocksize = 1KB
Operating Systems – CSCI 402
…
0
1
2
3
…
7
8
9
10
11
12
to make math easier
Disk Map contains 13 disk block pointers
a disk block pointer is just a block number
pointers 0 through 9 are direct pointers pointer 10 is an indirect pointer
pointer 11 is an double-indirect pointer pointer 12 is an triple-indirect pointer
321 0
53
Copyright ý . Systems – CSCI 402
i-list Data Region
inode
Disk Map
assuming blocksize = 1KB up to 10KB
…
0
1
2
3
…
7
8
9
10
11
12
Disk Map contains 13 disk block pointers
a disk block pointer is just a block number
Some blocks in the data region contains data
54
321 0
Copyright ý . Systems – CSCI 402
i-list Data Region
inode
Disk Map
assuming blocksize = 1KB up to 10KB+256KB
…
0
1
2
3
…
7
8
9
10
11
12
256 max entries
Disk Map contains 13 disk block pointers
a disk block pointer is just a block number
Some blocks in the data region contains data
some blocks in the data region contains data structures
Copyright ý . Cheng
55
321 0

Operating Systems – CSCI 402
i-list Data Region
inode
Disk Map
assuming blocksize = 1KB up to 10KB+256KB+64MB
…
0
1
2
3
…
7
8
9
10
11
12
256 max entries
256 max entries
256 max entries
256 max entries
56
321 0
Copyright ý . Cheng

limit set at 2GB
Operating Systems – CSCI 402
i-list Data Region
inode
Disk Map
assuming blocksize = 1KB
up to 10KB+256KB+64MB+16GB
…
0
1
2
3
…
7
8
9
10
11
12
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
57
321 0
Copyright ý . Systems – CSCI 402
i-list Data Region
inode
Disk Map
Content of File (i.e., File “Data”)
…
0
1
2
3
…
7
8
9
10
11
12
256 max entries
256 max entries
File “Metadata”
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
58
321 0
Copyright ý . Systems – CSCI 402
i-list Data Region
inode
Disk Map
Content of File (i.e., File “Data”)
for a directory file,
the lookup table is the “file content”
…
0
1
2
3
…
7
8
9
10
11
12
256 max entries
256 max entries
File “Metadata”
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
256 max entries
59
321 0
Copyright ý . Systems – CSCI 402
S5FS Free List
Free
Disk Block
0
1
…
97
98
99
free list head
Super Block
(un-used)
0
97
98
99
The superblock contains the addresses of up to 100 free disk blocks
the last of these disk blocks contains 100 pointers to additional free disk blocks, etc.
can find all the free disk blocks this way
321 0
60
Copyright ý . Systems – CSCI 402
S5FS Free List: Allocation – Case (1)
Free
Disk Block
0
1
…
97
98
99
free list head
Super Block
(un-used)
0
…
97
98
99
Need a free block
return first available block in first node of the free list (in superblock)
61
321 0
Copyright ý . Systems – CSCI 402
S5FS Free List: Allocation – Case (1)
Free
Disk Block
NULL
1
…
97
98
99
free list head
return this block
super block is cached in memory
no need to read from disk
Super Block
(un-used)
0
…
97
98
99
Need a free block
return first available block in first node of the free list (in superblock)
62
321 0
Copyright ý . Systems – CSCI 402
S5FS Free List: Allocation – Case (2)
NULL
NULL
…
NULL
NULL
99
free list head
Super Block
(un-used)
0
…
97
98
99
Need a free block
return first available block in first node of the free list (in superblock) if no free block in first node
first copy 100 pointers into the
superblock with one disk access
321 0
63
Copyright ý . Systems – CSCI 402
S5FS Free List: Allocation – Case (2)
0
1
…
97
98
99
free list head
Super Block
(un-used)
0
…
97
98
99
Need a free block
return first available block in first node of the free list (in superblock) if no free block in first node
first copy 100 pointers into the
superblock with one disk access
321 0
64
Copyright ý . Systems – CSCI 402
S5FS Free List: Allocation – Case (2)
0
1
…
97
98
99
free list head
one disk read to copy disk block pointers only happens 1 out of 100 allocations
return this block since it has been unlinked from the free list
Super Block
(un-used)
0
…
97
98
99
Need a free block
return first available block in first node of the free list (in superblock) if no free block in first node
first copy 100 pointers into the
superblock with one disk access
321 0
65
Copyright ý . Cheng