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

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

˛ Additional rmiregistry notes on the newsgroup

CMPSCI 377: Operating Systems Lecture 15, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: File System Functionality

Remember the high-level view of the OS as a translator from the user

abstraction to the hardware reality.

User Abstraction Hardware Resource

Processes/Threads CPU

Address Space (= OS =) Memory

Files Disk

CMPSCI 377: Operating Systems Lecture 15, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

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 15, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

User Requirements on Data

˛ Persistence: data stays around between jobs, power cycles, crashes

˛ Speed: can get to data quickly

˛ Size: can store lots of data

˛ Sharing/Protection: users can share data where appropriate or keep it

private when appropriate

˛ Ease of Use: user can easily Żnd, examine, modify, etc. data

CMPSCI 377: Operating Systems Lecture 15, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Hardware/OS Features

˛ Hardware provides:

{ Persistence: Disks provide non-volatile memory

{ Speed: Speed gained through random access

{ Size: Disks keep getting bigger (typical disk on a PC=20-100GB)

˛ OS provides:

{ Persistence: redundancy allows recovery from some additional failures

{ Sharing/Protection: Unix provides read, write, execute privileges for

Żles

{ Ease of Use

¤ Associating names with chunks of data (Żles)

¤ Organize large collections of Żles into directories

¤ Transparent mapping of the user's concept of Żles and directories

onto locations on disks

CMPSCI 377: Operating Systems Lecture 15, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Files

˛ File: Logical unit of storage on a storage device

{ Formally, named collection of related information recorded on

secondary storage

{ Examples: reader.cc, a.out

˛ Files can contain programs (source, binary) or data

˛ Files can be structured or unstructured

{ Unix implements Żles as a series of bytes (unstructured)

{ IBM mainframes implements Żles as a series of records or objects

(structured)

˛ File attributes: name, type, location, size, protection, creation time

CMPSCI 377: Operating Systems Lecture 15, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

User Interface to the File System

Common Żle operations:

Data operations:

˛ Create()

˛ Delete()

˛ Open()

˛ Close()

˛ Read()

˛ Write()

˛ Seek()

Naming operations: Attributes (owner, protection,: : :):

˛ HardLink()

˛ SoftLink()

˛ Rename()

˛ SetAttribute()

˛ GetAttribute()

CMPSCI 377: Operating Systems Lecture 15, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

OS File Data Structures

1. Open Żle table - shared by all processes with an open Żle.

˛ open count

˛ Żle attributes, including ownership, protection information, access

times, ...

˛ location(s) of Żle on disk

˛ pointers to location(s) of Żle in memory

2. Per-process Żle table - for each Żle,

˛ pointer to entry in the open Żle table

˛ current position in Żle (o®set)

˛ mode in which the process will access the Żle (r, w, rw)

˛ pointers to Żle bu®er

CMPSCI 377: Operating Systems Lecture 15, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Operations: Creating a File

˛ Create(name)

{ Allocate disk space (check disk quotas, permissions, etc.)

{ Create a Żle descriptor for the Żle including name, location on disk,

and all Żle attributes.

{ Add the Żle descriptor to the directory that contains the Żle.

{ Optional Żle attribute: Żle type (Word Żle, executable, etc.)

¤ Advantages: better error detection, specialized default operations

(double-clicking on a Żle knows what application to start), enables

storage layout optimizations

¤ Disadvantages: makes the Żle system and OS more complicated,

less °exible for user.

¤ Unix opts for simplicity (no Żle types), Macintosh/Windows opt for

user-friendliness

CMPSCI 377: Operating Systems Lecture 15, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Operations: Deleting a File

˛ Delete(name)

{ Find the directory containing the Żle.

{ Free the disk blocks used by the Żle.

{ Remove the Żle descriptor from the directory.

CMPSCI 377: Operating Systems Lecture 15, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Operation: Opening Files

˛ ŻleId = Open(name, mode)

{ Check if the Żle is already open by another process. If not:

¤ Find the Żle.

¤ Copy the Żle descriptor into the system-wide open Żle table.

{ Check the protection of the Żle against the requested mode. If not ok,

abort

{ Increment the open count.

{ Create an entry in the process's Żle table pointing to the entry in the

system-wide Żle table. Initialize the current Żle pointer to the start of

the Żle.

CMPSCI 377: Operating Systems Lecture 15, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Operations: Closing Files

˛ Close(ŻleId)

{ Remove the entry for the Żle in the process's Żle table.

{ Decrement the open count in the system-wide Żle table.

{ If the open count == 0, remove the entry in the system-wide Żle table.

CMPSCI 377: Operating Systems Lecture 15, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

OS File Operations: Reading a File

˛ Read(ŻleID, size, bufAddress) - sequential access (tape model)

{ OS reads \size" bytes from current Żle position, fp, into \bufAddress"

and increments current Żle position by size

for (i = 0; i < size; i++)

bufAddress[i] = file[fp + i];

fp += size;

˛ Read(ŻleID, from, size, bufAddress) - random access (disk model)

{ OS reads \size" bytes from Żle position \from" into \bufAddress"

for (i = from; i < from + size; i++)

bufAddress[i - from] = file[i];

CMPSCI 377: Operating Systems Lecture 15, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

OS File Operations

˛ Write is similar to reads, but copies from the bu®er to the Żle.

˛ Seek just updates fp.

˛ Memory mapping a Żle

{ Map a part of the portion virtual address space to a Żle

{ Read/write to that portion of memory )OS reads/writes from

corresponding location in the Żle

{ File accesses are greatly simpliŻed (no read/write call are necessary)

CMPSCI 377: Operating Systems Lecture 15, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

File Access Methods

˛ Common Żle access patterns from the programmer's perspective

{ Sequential: data processed in order, a byte or record at a time.

¤ Most programs use this method

¤ Example: compiler reading a source Żle.

{ Keyed: address a block based on a key value.

¤ Example: database search, hash table, dictionary

˛ Common Żle access patterns from the OS perspective:

{ Sequential: keep a pointer to the next byte in the Żle. Update the

pointer on each read/write.

{ Random: address any block in the Żle directly given its o®set within

the Żle.

CMPSCI 377: Operating Systems Lecture 15, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Naming and Directories

˛ Need a method of getting back to Żles that are left on disk.

˛ OS uses numbers for each Żle

˛ Users prefer textual names to refer to Żles.

{ Directory: OS data structure to map names to Żle descriptors

CMPSCI 377: Operating Systems Lecture 15, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Naming and Directories

˛ Naming strategies

{ Single-Level Directory: One name space for the entire disk, every

name is unique.

1. Use a special area of disk to hold the directory.

2. Directory contains <name, index> pairs.

3. If one user uses a name, no one else can.

4. Some early computers used this strategy. Early personal computers

also used this strategy because their disks were very small.

{ Two Level Directory: each user has a separate directory, but all of

each user's Żles must still have unique names

CMPSCI 377: Operating Systems Lecture 15, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Naming Strategies (cont)

˛ Multilevel Directories - tree structured name space (Unix, and all other

modern operating systems).

1. Store directories on disk, just like Żles except the Żle descriptor for

directories has a special °ag (indicating Żle or directory).

2. User programs read directories just like any other Żle, but only special

system calls can write directories.

3. Each directory contains <name, ŻleDesc> pairs in no particular order.

The Żle referred to by a name may be another directory.

4. There is one special root directory. Example: How do we look up

name: /usr/local/bin/netscape

CMPSCI 377: Operating Systems Lecture 15, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Referential naming (hard links)

˛ Hard links (Unix: ln command)

{ A hard link adds a second connection to a Żle

{ Example: creating a hard link from B to A

Initially: A ! Żle #100

After \ln A B": A ! Żle #100

B ! Żle #100

{ OS maintains reference counts, so it will only delete a Żle after the last

link to it has been deleted.

CMPSCI 377: Operating Systems Lecture 15, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Referential naming (hard links)

˛ Problem: user can create circular links with directories and then the OS

can never delete the disk space.

˛ Solution: No hard links to directories

A B

C

D E

F

data

data

data

CMPSCI 377: Operating Systems Lecture 15, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Referential Naming

˛ Soft links (Unix: ln -s command)

{ A soft link only makes a symbolic pointer from one Żle to another.

{ Example: creating a soft link from B to A

Initially: A ! Żle #100

After \ln A B": A ! Żle #100

B ! A

{ removing B does not a®ect A

{ removing A leaves the name B in the directory, but its contents no

longer exists

{ Problem: circular links can cause inŻnite loops (e.g., trying to list all

the Żles in a directory and its subdirectories)

{ Solution: limit number of links traversed.

CMPSCI 377: Operating Systems Lecture 15, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Directory Operations

˛ Search for a Żle: locate an entry for a Żle

˛ Create a Żle: add a directory listing

˛ Delete a Żle: remove directory listing

˛ List a directory: list all Żles (ls command in UNIX)

˛ Rename a Żle

˛ Traverse the Żle system

CMPSCI 377: Operating Systems Lecture 15, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Protection

˛ The OS must allow users to control sharing of their Żles )control access

to Żles

˛ Grant or deny access to Żle operations depending on protection

information

˛ Access control bits (UNIX)

{ Three categories of users (owner, group, world)

{ Three types of access privileges (read, write, execute)

{ Maintain a bit for each combination (111101000 = rwxr-x|)

˛ Access lists and groups (Windows NT, Andrew File System)

{ Keep an access list for each Żle with user name and type of access

{ Lists can become large and tedious to maintain

CMPSCI 377: Operating Systems Lecture 15, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary of File System Functionality

˛ Naming

˛ Protection

˛ Persistence

˛ Fast access

CMPSCI 377: Operating Systems Lecture 15, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

˛ Friday: come with questions about HW 3

˛ Monday: File System Implementation Issues (Chapter 11)

CMPSCI 377: Operating Systems Lecture 15, Page 25