DOC PREVIEW
U of I CS 241 - File System Implementation

This preview shows page 1-2-3-18-19-36-37-38 out of 38 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 System Programming File System Implementation (VI)ContentAdministrativeLinked AllocationLinked List Allocation IssuesSlide 6Slide 7File Allocation TableSlide 9Indexed AllocationSlide 11Slide 12Other Forms of Indexed File LinkedOther Forms of Indexed File - Multilevel IndexUNIX I-NodeQuestionsLevels of Access MethodsLevels of Access Methods (2)Levels of Access Methods (3)Levels of Access Methods (4)Implementing Directories (1)Implementing Directories (2)Shared Files (1)Shared Files (2)Free Space ManagementSlide 26Slide 27Slide 28Disk Space Management (1)Disk Space Management (2)File System ReliabilityFile System ConsistencyFile System PerformanceFile System Performance (Caching)File System Performance (Block Read Ahead)File System Performance (Reduce Disk Arm Motion)Log-Structured File Systems (LFS)Slide 38CS241 System ProgrammingFile System Implementation (VI)Klara NahrstedtLecture 253/27/200601/13/19 CS 241 - System Programming, Klara Nahrstedt2Content Previous Lecture: –Allocation of Disk Space Contiguous Allocation Allocation of Disk Space–Linked List Allocation–Indexed AllocationImplementation of DirectoriesDisk Space Management File System Reliability File System Performance01/13/19 CS 241 - System Programming, Klara Nahrstedt3Administrative MP3 is posted, due April 3, 2006Quiz 7 is March 31, 200601/13/19 CS 241 - System Programming, Klara Nahrstedt4Linked Allocation01/13/19 CS 241 - System Programming, Klara Nahrstedt5Linked List Allocation IssuesEach file is a linked list of chunksPointers in list are not accessible to userDirectory table maps files into head of list for a fileA node in the list can be a fixed size physical block or a contiguous collection of blocksEasy to use - no estimation of size necessary01/13/19 CS 241 - System Programming, Klara Nahrstedt6Linked List Allocation IssuesCan grow in middle and at endsSpace efficient, little fragmentationSlow - defies the principle of locality. Need to read through linked list nodes sequentially to find record of interest blocksSuited for sequential access but not direct access01/13/19 CS 241 - System Programming, Klara Nahrstedt7Linked List Allocation IssuesDisk space must be used to store pointers (if disk block is 512 bytes, and disk address requires 4 bytes, then the user sees blocks of 508 bytes)Not very reliable. System crashes can scramble files being updatedImportant variation on linked allocation method: `file-allocation table' (FAT) - OS/2 and MS-DOS01/13/19 CS 241 - System Programming, Klara Nahrstedt8File Allocation Table012345674672-11File A Starts here-1File B starts here01/13/19 CS 241 - System Programming, Klara Nahrstedt9Linked List Allocation IssuesSummary: linked allocation solves the external fragmentation and size-declaration problems of contiguous allocation,However, it can't support efficient direct access01/13/19 CS 241 - System Programming, Klara Nahrstedt10Indexed Allocation01/13/19 CS 241 - System Programming, Klara Nahrstedt11Indexed AllocationSolves external fragmentationSupports sequential, direct and indexed accessAccess requires at most one access to index block first. This can be cached in main memory01/13/19 CS 241 - System Programming, Klara Nahrstedt12Indexed AllocationFile can be extended by rewriting a few blocks and index blockRequires extra space for index block, possible wasted spaceExtension to big files issues01/13/19 CS 241 - System Programming, Klara Nahrstedt13Other Forms of Indexed FileLinkedLink full index blocks together using last entry.01/13/19 CS 241 - System Programming, Klara Nahrstedt14Other Forms of Indexed File - Multilevel Index Multiple levels of index blocks01/13/19 CS 241 - System Programming, Klara Nahrstedt15UNIX I-Node01/13/19 CS 241 - System Programming, Klara Nahrstedt16QuestionsWhich of the following is not a problem associated with contiguous allocation of disk space for a file? –External fragmentation of disk space or –Frequent copying or –Direct accessWhich of the following methods would you choose if the file requires frequent direct access and also external fragmentation is to be avoided (to keep disk utilization high)?–Linked allocation or –Contiguous allocation or –Indexed allocation01/13/19 CS 241 - System Programming, Klara Nahrstedt17Levels of Access MethodsBlock level access to a file is in terms of blocks or physical records within a fileUser must do his own buffering. Access methods include: –Read(file, block_no)–Write(file, block_no)–Wait(file, block_no)01/13/19 CS 241 - System Programming, Klara Nahrstedt18Levels of Access Methods (2)File level access to the file is in terms of acquiring access to a copy of the file that is stored in primary memoryQueued or buffered level access to the file is in terms of logical records that depend on software interpretation. –For example, read and write chars in UNIX. Buffering is used to provide logical record abstraction and maps i/o into physical records01/13/19 CS 241 - System Programming, Klara Nahrstedt19Levels of Access Methods (3)Memory-mapped file level –the file is mapped into virtual memory –file access is at the instruction level –page faults may read file data chunks from disk to memory –an address of a logical record within a file is given by a virtual memory address offset of that record from the beginning of the file01/13/19 CS 241 - System Programming, Klara Nahrstedt20Levels of Access Methods (4)Persistent object –the file is mapped into virtual memory and –access to the contents of the file is provided by an abstract data type interface that is determined by –the type of the data stored in the file01/13/19 CS 241 - System Programming, Klara Nahrstedt21Implementing Directories (1)(a) A simple directoryfixed size entriesdisk addresses and attributes in directory entry(b) Directory in which each entry just refers to an i-node01/13/19 CS 241 - System Programming, Klara Nahrstedt22Implementing Directories (2)Two ways of handling long file names in directory(a) In-line or (b) In a heap01/13/19 CS 241 - System Programming, Klara Nahrstedt23Shared Files (1)File system containing a shared file01/13/19 CS 241 - System Programming, Klara Nahrstedt24Shared Files (2)(a) Situation prior to linking(b) After the link is created(c) After the original owner removes the file01/13/19 CS 241 - System Programming, Klara Nahrstedt25Free Space


View Full Document

U of I CS 241 - File System Implementation

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download File System Implementation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view File System Implementation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view File System Implementation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?