DOC PREVIEW
U of I CS 241 - System Programming File System Implementation (V)

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 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 22 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 22 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 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS241 System ProgrammingFile System Implementation (V)ContentAdministrativeFile System LayoutFile System ImplementationAllocation of Disk SpaceContiguous AllocationContiguous Allocation IssuesContiguous Allocation IssuesLinked AllocationLinked List Allocation IssuesLinked List Allocation IssuesLinked List Allocation IssuesFile Allocation TableLinked List Allocation IssuesIndexed AllocationIndexed AllocationIndexed AllocationOther Forms of Indexed FileLinkedOther Forms of Indexed File - Multilevel IndexUNIX I-NodeQuestionsCS241 System ProgrammingFile System Implementation (V)Klara NahrstedtLecture 243/17/20063/12/2006CS 241 - System Programming, Klara Nahrstedt2Content z File System Layoutz Allocation of Disk Space– Contiguous Allocation – Linked List Allocation– Indexed Allocation3/12/2006CS 241 - System Programming, Klara Nahrstedt3Administrative z R: Ch 4 pp92-135z MP3 is posted, due April 3, 2006z Quiz 6 is March 17, 20063/12/2006CS 241 - System Programming, Klara Nahrstedt4File System Layoutz Most disks are divided up to one or more partitionswith independent file systems in each partitionz Sector 0 is called MBR – Master Boot Record– Used to boot the computer– End of MBR contains partition table– MBR is executed by BIOS, BIOS is read when computer is booted– MBR locates active partition, reads boot block, executes it– Boot block includes OS in that partitionz Superblock – key parameters about the file system – Magic number to identify the file system type, number of blocks in the file system, other key admin information3/12/2006CS 241 - System Programming, Klara Nahrstedt5File System ImplementationA possible file system layout3/12/2006CS 241 - System Programming, Klara Nahrstedt6Allocation of Disk Spacez Low level access methods depend upon the disk allocation scheme used to store file data – Contiguous allocation– Linked list allocation– Block allocation3/12/2006CS 241 - System Programming, Klara Nahrstedt7Contiguous Allocation3/12/2006CS 241 - System Programming, Klara Nahrstedt8Contiguous Allocation Issuesz Access method suits sequential and direct accessz Directory table maps files into starting physical address and lengthz Easy to recover in event of system crashz Fast, often requires no head movement and when it does, head only moves one track3/12/2006CS 241 - System Programming, Klara Nahrstedt9Contiguous Allocation Issuesz File is allocated large contiguous chunksz User knows size of the filez Expanding the file requires copyingz Dynamic storage allocation - first fit, best fitz External fragmentation occurs on diskz Users tend to overestimate space => internal fragmentation3/12/2006CS 241 - System Programming, Klara Nahrstedt10Linked Allocation3/12/2006CS 241 - System Programming, Klara Nahrstedt11Linked List Allocation Issuesz Each file is a linked list of chunksz Pointers in list are not accessible to userz Directory table maps files into head of list for a filez A node in the list can be a fixed size physical block or a contiguous collection of blocksz Easy to use - no estimation of size necessary3/12/2006CS 241 - System Programming, Klara Nahrstedt12Linked List Allocation Issuesz Can grow in middle and at endsz Space efficient, little fragmentationz Slow - defies the principle of locality. Need to read through linked list nodes sequentially to find record of interest blocksz Suited for sequential access but not direct access3/12/2006CS 241 - System Programming, Klara Nahrstedt13Linked List Allocation Issuesz 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)z Not very reliable. System crashes can scramble files being updatedz Important variation on linked allocation method: `file-allocation table' (FAT) - OS/2 and MS-DOS3/12/2006CS 241 - System Programming, Klara Nahrstedt14File Allocation Table012344672-11567-1File A Starts hereFile B starts here3/12/2006CS 241 - System Programming, Klara Nahrstedt15Linked List Allocation Issuesz Summary: linked allocation solves the external fragmentation and size-declaration problems of contiguous allocation,z However, it can't support efficient direct access3/12/2006CS 241 - System Programming, Klara Nahrstedt16Indexed Allocation3/12/2006CS 241 - System Programming, Klara Nahrstedt17Indexed Allocationz Solves external fragmentationz Supports sequential, direct and indexed accessz Access requires at most one access to index block first. This can be cached in main memory3/12/2006CS 241 - System Programming, Klara Nahrstedt18Indexed Allocationz File can be extended by rewriting a few blocks and index blockz Requires extra space for index block, possible wasted spacez Extension to big files issues3/12/2006CS 241 - System Programming, Klara Nahrstedt19Other Forms of Indexed FileLinkedLink full index blocks together using last entry.3/12/2006CS 241 - System Programming, Klara Nahrstedt20Other Forms of Indexed File -Multilevel IndexMultiple levels of index blocks3/12/2006CS 241 - System Programming, Klara Nahrstedt21UNIX I-Node3/12/2006CS 241 - System Programming, Klara Nahrstedt22Questionsz 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 accessz 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


View Full Document

U of I CS 241 - System Programming File System Implementation (V)

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 System Programming File System Implementation (V)
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 System Programming File System Implementation (V) 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 System Programming File System Implementation (V) 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?