Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Last Class: File System Abstraction

Seek() ReadBlock() WriteBlock()

Sectors

Applications Daemons Servers Shell

Interface

Tracks

Interface

Programmer

Device

Interface

Indepedent

Device

Open() Write() Read() Close()

Link() Rename()

Hardware

Disk

CMPSCI 377: Operating Systems Lecture 16, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: File System Implementation

Disk management

˛ Brief review of how disks work.

˛ How to organize data on to disks.

CMPSCI 377: Operating Systems Lecture 16, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

How Disks Work

Surface

Sectors / Blocks

Disk

Track / Cylinder

Head

˛ The disk surface is circular and is coated with a magnetic material. The

disk is always spinning (like a CD).

˛ Tracks are concentric rings on disk with bits laid out serially on tracks.

˛ Each track is split into sectors or blocks, the minimum unit of transfer

from the disk

CMPSCI 377: Operating Systems Lecture 16, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Disk Usage Overhead

˛ Overhead: time the CPU takes to start a disk operation

˛ Latency: the time to initiate a disk transfer of 1 byte to memory.

{ Seek time: time to position the head over the correct cylinder

{ Rotational time: the time for the correct sector to rotate under the

head

{ Transfer time: the time required to move the bytes o® the disk to the

disk controller

˛ Bandwidth: once a transfer is initiated, the rate of I/O transfer

CMPSCI 377: Operating Systems Lecture 16, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

How Disks Work

˛ CDs come individually, but disks come organized in disk

pack consisting of a stack of platters.

˛ Disk packs use both sides of the platters, except on the

ends

˛ Comb has 2 read/write head assemblies at the end of

each arm.

˛ Cylinders are matching sectors on each surface.

˛ Disk operations are in terms of radial coordinates.

1. Move arm to correct track, waiting for the disk to

rotate under the head.

2. Select and transfer the correct sector as it spins by

CMPSCI 377: Operating Systems Lecture 16, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Organization on Disk

The information we need:

ŻleID 0, Block 0 ! Platter 0, cylinder 0, sector 0

ŻleID 0, Block 1 ! Platter 4, cylinder 3, sector 8

: : :

Key performance issues:

1. We need to support sequential and random access.

2. What is the right data structure in which to maintain Żle location

information?

) How do we lay out the Żles on the physical disk?

CMPSCI 377: Operating Systems Lecture 16, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Organization: On-Disk Data Structures

˛ The structure used to describe where the Żle is on the disk and the

attributes of the Żle is the Żle descriptor (FileDesc). File descriptors have

to be stored on disks just like Żles.

˛ Most systems Żt the following proŻle:

1. Most Żles are small.

2. Most disk space is taken up by large Żles.

3. I/O operations target both small and large Żles.

=) The per-Żle cost must be low, but large Żles must also have good

performance.

CMPSCI 377: Operating Systems Lecture 16, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Contiguous Allocation

˛ OS maintains an ordered list of free disk blocks

˛ OS allocates a contiguous chunk of free blocks when it creates a Żle.

˛ Need to store only the start location and size in the Żle descriptor

˛ Advantages

{

{ Access time?

{ Number of seeks?

˛ Disadvantages

{

{ Fragmentation?

{ Disk management?

CMPSCI 377: Operating Systems Lecture 16, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Contiguous Allocation

˛ OS maintains an ordered list of free disk blocks

˛ OS allocates a contiguous chunk of free blocks when it creates a Żle.

˛ Need to store only the start location and size in the Żle descriptor

˛ Advantages

{ Simple

{ Access time? Slow for Żrst block, quick after that

{ Number of seeks? 1 for each track it spans, adjacent tracks

CMPSCI 377: Operating Systems Lecture 16, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Contiguous Allocation (cont)

˛ Disadvantages

{ Changing Żle size is hard

{ Fragmentation? External: Żles scattered all over disk

{ Disk management? Need compaction

˛ Examples: IBM OS/360, write-only disks, early personal computers

CMPSCI 377: Operating Systems Lecture 16, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Linked Żles

˛ Keep a list of all the free sectors/blocks.

˛ In the Żle descriptor, keep a pointer to the Żrst sector/block.

˛ In each sector, keep a pointer to the next sector.

4

5

2

1

8

0

1

9

7 12 3 20

sector

platter

cylinder

sector

platter

cylinder

sector

platter

cylinder

sector

platter

cylinder

Descriptor

File

data data data data

CMPSCI 377: Operating Systems Lecture 16, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Linked Files

˛ Advantages:

{ Fragmentation?

{ File size changes?

{ E±ciently supports which type of access?

˛ Disadvantages:

{ Does not support which type of access? Why?

{ Number of seeks?

CMPSCI 377: Operating Systems Lecture 16, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Linked Files

˛ Advantages:

{ Fragmentation? Internal (Żle scattered all over the disk)

{ File size changes? Easy: link on a new block

{ E±ciently supports which type of access? Sequential

˛ Disadvantages:

{ Does not support which type of access? Why? Random: must follow

entire chain to get to the desired block

{ Number of seeks? 1 / block

˛ Examples: MS-DOS

CMPSCI 377: Operating Systems Lecture 16, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Indexed Files

˛ OS keeps an array of block pointers for each

Żle. This array is stored in an index block on

the disk.

˛ OS allocates the index block to hold the pointers

to all the blocks when it creates the Żle, but

allocates the blocks only on demand.

˛ OS Żlls in the pointers as it allocates blocks.

Descriptor

File

CMPSCI 377: Operating Systems Lecture 16, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Indexed Files

˛ Advantages

{

{

˛ Disadvantages

{

{

CMPSCI 377: Operating Systems Lecture 16, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Indexed Żles

˛ Advantages

{ Not much wasted space (although we pay a price for small Żles).

{ Both sequential and random accesses are easy.

˛ Disadvantages

{ Sets a maximum Żle size.

{ Lots of seeks because data is not contiguous.

˛ Examples: Nachos

CMPSCI 377: Operating Systems Lecture 16, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel Indexed Files

˛ Each Żle descriptor contains 14

block pointers.

˛ First 12 pointers point to data

blocks.

˛ 13th pointer points to a block

of 1024 pointers to 1024 more

data blocks. (One indirection.)

˛ 14th pointer points to a block

of pointers to indirect blocks.

(Two indirections.)

data

data

data

data

Descriptor

File

...

File

Index

Index

File

Index

File

Pointers to Index Files

mode

owners

timestamps

size

block count

CMPSCI 377: Operating Systems Lecture 16, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel indexed Żles: BSD UNIX 4.3

˛ Advantages

{

{

{

˛ Disadvantages

{

{

˛ Is the Żle size bounded?

˛ What could the OS do to get more contiguous access and fewer seeks?

CMPSCI 377: Operating Systems Lecture 16, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multilevel indexed Żles: BSD UNIX 4.3

˛ Advantages

{ Simple to implement

{ Supports incremental Żle growth

{ Small Żles?

˛ Disadvantages

{ Indirect access is ine±cient for random access to very large Żles.

{ Lots of seeks because data is not contiguous.

˛ Is the Żle size bounded? Yes, but very large

˛ What could the OS do to get more contiguous access and fewer seeks?

Cluster blocks

CMPSCI 377: Operating Systems Lecture 16, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Free-Space Management

˛ Need a free-space list to keep track of which disk blocks are free (just as

we need a free-space list for main memory)

˛ Need to be able to Żnd free space quickly and release space quickly )use

a bitmap

{ The bitmap has one bit for each block on the disk.

{ If the bit is 1, the block is free. If the bit is 0, the block is allocated.

˛ Can quickly determine if any page in the next 32 is free, by comparing the

word to 0. If it is 0, all the blocks are in use. Otherwise, you can use bit

operations to Żnd an empty block.

110000100100011111110...

˛ Marking a block as freed is simple since the block number can be used to

index into the bitmap to set a single bit.

CMPSCI 377: Operating Systems Lecture 16, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Free-Space Management

˛ Problem: Bitmap might be too big to keep in memory for a large disk. A

2 GB disk with 512 byte sectors requires a bitmap with 4,000,000 entries

(500,000 bytes).

˛ If most of the disk is in use, it will be expensive to Żnd free blocks with a

bitmap.

˛ An alternative implementation is to link together the free blocks.

{ The head of the list is cached in kernel memory. Each block contains a

pointer to the next free block.

{ How expensive is it to allocate a block?

{ How expensive is it to free a block?

{ How expensive is it to allocate consecutive blocks?

CMPSCI 377: Operating Systems Lecture 16, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Directory Representations

For each directory, must keep a list of Żle names + references to the

associated Żle descriptors.

˛ Stored in special blocks.

˛ How to organize the list?

{ Linear: simple, but can be expensive to perform lookup operations.

{ Linear but sorted: lookup is very cheap, but maintenance is hard.

{ Hash table: lookup can be very cheap; maintenance is also cheap. But

- implementation is more complex.

CMPSCI 377: Operating Systems Lecture 16, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

˛ Many of the concerns and implementations of Żle system

implementations are similar to those of virtual memory implementations.

{ Contiguous allocation is simple, but su®ers from external

fragmentation, the need for compaction, and the need to move Żles as

they grow.

{ Indexed allocation is very similar to page tables. A table maps from

logical Żle blocks to physical disk blocks.

{ Free space can be managed using a bitmap or a linked list.

CMPSCI 377: Operating Systems Lecture 16, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

˛ Wednesday: Introduction to lab 4

˛ Wednesday/Friday: Memory Management: Chapter 9

CMPSCI 377: Operating Systems Lecture 16, Page 24