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 AllocationImplementation of DirectoriesDisk Space Management File System Reliability File System Performance01/13/19 CS 241 - System Programming, Klara Nahrstedt3Administrative MP3 is posted, due April 3, 2006Quiz 7 is March 31, 200601/13/19 CS 241 - System Programming, Klara Nahrstedt4Linked Allocation01/13/19 CS 241 - System Programming, Klara Nahrstedt5Linked List Allocation IssuesEach file is a linked list of chunksPointers in list are not accessible to userDirectory table maps files into head of list for a fileA node in the list can be a fixed size physical block or a contiguous collection of blocksEasy to use - no estimation of size necessary01/13/19 CS 241 - System Programming, Klara Nahrstedt6Linked List Allocation IssuesCan grow in middle and at endsSpace efficient, little fragmentationSlow - defies the principle of locality. Need to read through linked list nodes sequentially to find record of interest blocksSuited for sequential access but not direct access01/13/19 CS 241 - System Programming, Klara Nahrstedt7Linked List Allocation IssuesDisk 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 updatedImportant 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 IssuesSummary: 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 AllocationSolves external fragmentationSupports sequential, direct and indexed accessAccess requires at most one access to index block first. This can be cached in main memory01/13/19 CS 241 - System Programming, Klara Nahrstedt12Indexed AllocationFile can be extended by rewriting a few blocks and index blockRequires extra space for index block, possible wasted spaceExtension 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 Nahrstedt16QuestionsWhich 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 accessWhich 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 MethodsBlock level access to a file is in terms of blocks or physical records within a fileUser 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 memoryQueued 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