CS代考 Operating Systems – CSCI 402 – cscodehelp代写

Operating Systems – CSCI 402
S5FS Free List: Deallocation – Case (1)
Free Me
NULL
1
…
97
98
99
Free
Disk Block
free list head
Super Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock
4
321 0
Copyright ý . 5FS Free List: Deallocation – Case (1)
super block is cached in memory
no need to write to disk
Operating Systems – CSCI 402
Free
Disk Block
0
1
…
97
98
99
free list head
Super Block
Free
Disk Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock
5
321 0
Copyright ý . Systems – CSCI 402
S5FS Free List: Deallocation – Case (2)
Free
Disk Block
0
1
…
97
98
99
free list head
Free Me
Super Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock if the list is full
copy first node from super block
into the newly freed block and update superblock
321 0
Copyright ý . Cheng
6

Operating Systems – CSCI 402
S5FS Free List: Deallocation – Case (2)
0
1
…
99
Free
Disk Block
0
1
…
97
98
99
free list head
Super Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock if the list is full
copy first node from super block
into the newly freed block and update superblock
321 0
7
Copyright ý . 5FS Free List: Deallocation – Case (2)
Operating Systems – CSCI 402
0
1
…
99
Free
Disk Block
NULL
NULL
…
NULL
NULL
99
free list head
Super Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock if the list is full
copy first node from super block
into the newly freed block and update superblock
321 0
8
Copyright ý . 5FS Free List: Deallocation – Case (2)
one disk write to copy disk block pointers only happens 1 out of 100 frees
Operating Systems – CSCI 402
0
1
…
99
Free
Disk Block
NULL
NULL
…
NULL
NULL
99
free list head
Super Block
(un-used)
0
…
97
98
99
When a disk block is freed
that block¡¯s address is added to the list of free blocks in the superblock if the list is full
copy first node from super block
into the newly freed block and update superblock
321 0
9
Copyright ý . Systems – CSCI 402
S5FS Free List
Why 100 disk pointers in each free block?
to reduce the number of disk accesses
for every 100 times you need to allocate/deallocate a free block, you only need to go to the disk 1 time (on the average)
effective allocation/deallocation time is 100 times faster!
is the reason also to reduces the length of the free list?
no
but reducing the length of the free list reduces the number of disk accesses
correct, but that¡¯s a secondary effect
it¡¯s important to be able to distinguish between what¡¯s primary and what¡¯s secondary effects
10
321 0
Copyright ý . Block
Inodes (in the i-list) are marked free (0) or not free (1)
I-list
Operating Systems – CSCI 402
S5FS Free Inode List
4
12
6
11
…
13
inode cache
11 21 31 40 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
… …
use a “bitmap” to store this
no additional organization in the i-list
the superblock caches free inodes (i.e., in the inode cache) 11
321 0
Copyright ý . Systems – CSCI 402
S5FS Free Inode List
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 40 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
… …
Super Block
can store location of bitmap, # of inodes, etc. in super block bitmap can be cached in memory for speed
Inodes (in the i-list) are marked free (0) or not free (1)
I-list
use a “bitmap” to store this
no additional organization in the i-list
the superblock caches free inodes (i.e., in the inode cache) 12
321 0
Copyright ý . Systems – CSCI 402
S5FS Free Inode List
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 40 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
Super Block
The inode cache
to allocate an inode, simply
mark it not free and remove it from the inode cache
to free an inode, simply mark it free and add to the inode cache if there is room
Copyright ý . Cheng
… …
I-list
13
321 0

Operating Systems – CSCI 402
S5FS Free Inode List: Allocation – Case (1)
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 40 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
Super Block
If the inode cache is not empty mark an inode not free and remove it from the inode cache
ex: need a free inode
Copyright ý . Cheng
… …
I-list
14
321 0

Operating Systems – CSCI 402
S5FS Free Inode List: Allocation – Case (1)
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 41 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
Super Block
If the inode cache is not empty mark an inode not free and remove it from the inode cache
Copyright ý . Cheng
ex: need a free inode
inode 4 is now allocated (i.e., not free)
321 0
… …
I-list
15

Super Block
If the inode cache is empty scan the i-list to refill it
I-list
to help out with the scan, the super block keeps the first free inode in the i-list (“low water mark”)
Operating Systems – CSCI 402
S5FS Free Inode List: Allocation – Case (2)
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 41 51 61 71 81 91
10 1 11 1 12 1 13 1 14 1 15 1
… …
need to maintain this entry when necessary
321 0
16
Copyright ý . Systems – CSCI 402
S5FS Free Inode List: Deallocation – Case (1)
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 41 51 60 71 81 90
10 1 11 0 12 1 13 0 14 1 15 1
Super Block
If the inode cache is not full
add inode number to inode cache I-list
update bitmap to indicate that the inode is now free update “low water mark” in super block if necessary
ex: free inode 8
Copyright ý . Cheng
… …
17
321 0

Operating Systems – CSCI 402
S5FS Free Inode List: Deallocation – Case (1)
boot
super
I-list
bitmap
data
8
12
6
11
…
13
inode cache
11 21 31 41 51 60 71 80 90
10 1 11 0 12 1 13 0 14 1 15 1
Super Block
If the inode cache is not full
add inode number to inode cache I-list
update bitmap to indicate that the inode is now free update “low water mark” in super block if necessary
ex: free inode 8
Copyright ý . Cheng
… …
18
321 0

Operating Systems – CSCI 402
S5FS Free Inode List: Deallocation – Case (2)
boot
super
I-list
bitmap
data
4
12
6
11
…
13
inode cache
11 21 31 40 51 60 71 81 90
10 1 11 0 12 0 13 0 14 1 15 1
Super Block
If the inode cache is full
no need to modify inode cache I-list
update bitmap to indicate that the inode is now free update “low water mark” in super block if necessary
Copyright ý . Cheng
… …
19
321 0

update i-list, inode cache, and “low water mark”
First write to a file
get a free block update free list
More writes to the file
may need to get a free block and update free list
To delete a file
add disk block(s) to free list
mark inode free in i-list, update inode cache and “low water mark”
Operating Systems – CSCI 402
To create a file get a free inode
S5FS Summary
20
321 0
Copyright ý . 5FS Summary
In designing a file system, one tries to minimize the number of disk operations
read vs. write
sequential access vs. random access
S5FS gives O(1) number of disk operations for random access
inode
Operating Systems – CSCI 402
Copyright ý . Cheng
21
321 0

Operating Systems – CSCI 402
6.1 The Basics of File Systems
UNIX¡¯s S5FS
Disk Architecture
Problems with S5FS Improving Performance
22
321 0
Copyright ý . Systems – CSCI 402
Disk Architecture
How do you get to a particular byte of data on the disk?
what does a disk look like?
Disk heads (on top and bottom of each platter)
Sector
Track
Clearly, this looks nothing like the S5FS layout
or any logical file system layout
321 0
23
Copyright ý .

Operating Systems – CSCI 402
Disk Architecture
Sector
Track
Disk heads (on top and bottom of each platter)
Smallest addressable unit is a sector
disk address = (head/surface#, cylinder/track#, sector#)
321 0
24
Copyright ý .

Disk access time: time to copy a sector from disk to controller access time = seek time + rotational latency + data transfer time
some people would use the term “response time” to mean “access time”, but we should avoid the use of the term
Operating Systems – CSCI 402
Rhinopias Disk Drive
Rotation speed
10,000 RPM
Number of surfaces
8
Sector size
512 bytes
Sectors/track
500-1000; 750 average
Tracks/surface
100,000
Storage capacity
307.2 billion bytes
Average seek time
4 milliseconds
One-track seek time
.2 milliseconds
Maximum seek time
10 milliseconds
“response time”
321 0
25
Copyright ý . Systems – CSCI 402
Ch 7: Memory Management
http://merlot.usc.edu/william/usc/
26
321 0
Copyright ý . Cheng