MCA613_System Programming and Operating System

Memory Management - 2 193 Difficult to implement:  One approach is to tag each page with the time of last reference. This requires a great deal of overhead. Example-2: LRU page replacement Algorithm Fig. 10.15: LRU Total Page Faults Not Recently Used (NRU) Page In order to allow the operating system to collect useful statistics about which pages are being used and which ones are not, most computers with virtual memory have two status bits associated with each page. R is set whenever the page is referenced (read or written). M is set when the page is written to (i.e., modified). The bits are contained in each page table entry. It is important to realize that these bits must be updated on every memory reference, so it is essential that they be set by the hardware. Once a bit has been set to 1, it stays 1 until the operating system resets it to 0 in software. If the hardware does not have these bits, they can be simulated as follows. When a process is started up, all of its page table entries are marked as not in memory. As soon as any page is referenced, a page fault will occur. The operating system then sets the R bit (in its internal tables), changes the page table entry to point to the correct page, with mode READ ONLY, and restarts the instruction. If the page is subsequently written on, another page fault will occur, allowing the operating system to set the M bit and change the page's mode to READ/WRITE. The R and M bits can be used to build a simple paging algorithm as follows. When a process is started up, both page bits for all its pages are set to 0 by the operating system. Periodically (e.g., CU IDOL SELF LEARNING MATERIAL (SLM)

194 System Programming and Operating System on each clock interrupt), the R bit is cleared, to distinguish pages that have not been referenced recently from those that have been. When a page fault occurs, the operating system inspects all the pages and divides them into four categories based on the current values of their R and M. Class 0: not referenced, not modified. Class 1: not referenced, modified Class 2: referenced, not modified. Class 3: referenced, modified. Although class 1 pages seem, at first glance, impossible, they occur when a class 3 page has its R bit cleared by a clock interrupt. Clock interrupts do not clear the M bit because this information is needed to know whether the page has to be rewritten to disk or not. Clearing R but not M leads to a class 1 page. The NRU (Not Recently Used) algorithm removes a page at random from the lowest numbered nonempty class. Implicit in this algorithm is that it is better to remove a modified page that has not been referenced in at least one clock tick (typically 20 msec) than a clean page that is in heavy use. The main attraction of NRU is that it is easy to understand, moderately efficient to implement, and gives a performance that, while certainly not optimal, may be adequate. The Clock Page Replacement Algorithm Although second chance is a reasonable algorithm, it is unnecessarily inefficient because it is constantly moving pages around on its list. A better approach is to keep all the page frames on a circular list in the form of a clock, as shown in Fig. 10.16. A hand points to the oldest page. When a page fault occurs, the page being pointed to by the hand is inspected. If its R bit is 0, the page is evicted, the new page is inserted into the clock in its place, and the hand is advanced one position. If R is 1, it is cleared and the hand is advanced to the next page. This process is repeated until a page is found with. CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 195 A LB KC When a page fault occurs, the page the hand is pointing to is inspected. J D The action taken depends on the R bit: R = 0: Evict the page I E R = 1: Clear R and advance hand HF G Fig. 10.16: The Clock Page Replacement Algorithm R = 0. Not surprisingly, this algorithm is called clock. It differs from second chance only in the implementation. Example for All the page replacement techniques: Page address stream OPT LRU FIFO CLOCK F = page fault occurring after the frame allocation is initially filled Fig. 10.17: All Page Replacement Algorithm CU IDOL SELF LEARNING MATERIAL (SLM)

196 System Programming and Operating System 10.4 Page Fault Handling Fig. 10.18: Page Fault Handling  The basic idea behind paging is that when a process is swapped in, the pager only loads into memory those pages that it expects the process to need (right away.)  Pages that are not loaded into memory are marked as invalid in the page table, using the invalid bit. (The rest of the page table entry may either be blank or contain information about where to find the swapped-out page on the hard drive.)  If the process only ever accesses pages that are loaded in memory (memory resident pages), then the process runs exactly as if all the pages were loaded in to memory. CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 197  On the other hand, if a page is needed that was not originally loaded up, then a page fault trap is generated, which must be handled in a series of steps:  The memory address requested is first checked, to make sure it was a valid memory request. (a) If the reference was invalid, the process is terminated. Otherwise, the page must be paged in. (b) A free frame is located, possibly from a free-frame list. (c) A disk operation is scheduled to bring in the necessary page from disk. (This will usually block the process on an I/O wait, allowing some other process to use the CPU in the meantime.) (d) When the I/O operation is complete, the process’s page table is updated with the new frame number, and the invalid bit is changed to indicate that this is now a valid page reference. The instruction that caused the page fault must now be restarted from the beginning, (as soon as this process gets another turn on the CPU.) In an extreme case, NO pages are swapped in for a process until they are requested by page faults. This is known as pure demand paging.  In theory each instruction could generate multiple page faults. In practice this is very rare, due to locality of reference, covered in Section 9.6.1.  The hardware necessary to support virtual memory is the same as for paging and swapping: A page table and secondary memory.  A crucial part of the process is that the instruction must be restarted from scratch once the desired page has been made available in memory. For most simple instructions this is not a major difficulty. However, there are some architectures that allow a single instruction to modify a fairly large block of data, (which may span a page boundary), and if some of the data gets modified before the page fault occurs, this could cause problems. One solution is to access both ends of the block before executing the instruction, guaranteeing that the necessary pages get paged in before the instruction begins. CU IDOL SELF LEARNING MATERIAL (SLM)

198 System Programming and Operating System 10.5 Working Set Model The basic principle states that if we allocate enough frames to a process to accommodate its current locality, it will only fault whenever it moves to some new locality. But if the allocated frames are lesser than the size of the current locality, the process is bound to thrash. According to this model, based on a parameter A, the working set is defined as the set of pages in the most recent ‘A’ page references. Hence, all the actively used pages would always end up being a part of the working set. The accuracy of the working set is dependent on the value of parameter A. If A is too large, then working sets may overlap. On the other hand, for smaller values of A, the locality might not be covered entirely. If D is the total demand for frames and WSSi is the working set size for a process i, D = ∑WSSi Now, if ‘m’ is the number of frames available in the memory, there are 2 possibilities: (i) D > m i.e. total demand exceeds the number of frames, then thrashing will occur as some processes would not get enough frames. (ii) D <= m, then there would be no thrashing. If there are enough extra frames, then some more processes can be loaded in the memory. On the other hand, if the summation of working set sizes exceeds the availability of frames, then some of the processes have to be suspended (swapped out of memory). This technique prevents thrashing along with ensuring the highest degree of multi- programming possible. Thus, it optimizes CPU utilization. 10.6 Local vs. Global Allocation The number of frames allocated to a process can also dynamically change depending on whether you have used global replacement or local replacement for replacing pages in case of a page fault. CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 199 1. Local replacement: When a process needs a page which is not in the memory, it can bring in the new page and allocate it a frame from its own set of allocated frames only.  Advantage: The pages in memory for a particular process and the page fault ratio are affected by the paging behaviour of only that process.  Disadvantage: A low priority process may hinder a high priority process by not making its frames available to the high priority process. 2. Global replacement: When a process needs a page which is not in the memory, it can bring in the new page and allocate it a frame from the set of all frames, even if that frame is currently allocated to some other process; that is, one process can take a frame from another.  Advantage: Does not hinder the performance of processes and hence results in greater system throughput.  Disadvantage: The page fault ratio of a process cannot be solely controlled by the process itself. The page in memory for a process depends on the paging behaviour of other processes as well. 10.7 Page Size Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non- contiguous.  Logical Address or Virtual Address (represented in bits): An address generated by the CPU CU IDOL SELF LEARNING MATERIAL (SLM)

200 System Programming and Operating System  Logical Address Space or Virtual Address Space (represented in words or bytes): The set of all logical addresses generated by a program  Physical Address (represented in bits): An address actually available on memory unit  Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding to the logical addresses Example:  If Logical Address = 31 bit, then Logical Address Space = 231 words = 2 G words (1 G = 230)  If Logical Address Space = 128 M words = 27 * 220 words, then Logical Address = log2 227 = 27 bits  If Physical Address = 22 bit, then Physical Address Space = 222 words = 4 M words (1 M = 220)  If Physical Address Space = 16 M words = 24 * 220 words, then Physical Address = log2 224 = 24 bits The mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device and this mapping is known as paging technique.  The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.  The Logical address Space is also splitted into fixed-size blocks, called pages.  Page Size = Frame Size Let us consider an example:  Physical Address = 12 bits, then Physical Address Space = 4 K words  Logical Address = 13 bits, then Logical Address Space = 8 K words  Page size = frame size = 1 K words (assumption) CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 201 Fig. 10.19: Process of Paging Address generated by CPU is divided into  Page number (p): Number of bits required to represent the pages in Logical Address Space or Page number  Page offset (d): Number of bits required to represent particular word in a page or page size of Logical Address Space or word number of a page or page offset. Physical Address is divided into  Frame number (f): Number of bits required to represent the frame of Physical Address Space or Frame number.  Frame offset (d): Number of bits required to represent particular word in a frame or frame size of Physical Address Space or word number of a frame or frame offset. The hardware implementation of page table can be done by using dedicated registers. But the usage of register for the page table is satisfactory only if page table is small. If page table CU IDOL SELF LEARNING MATERIAL (SLM)

202 System Programming and Operating System contain large number of entries then we can use TLB (translation Look-aside buffer), a special, small, fast look up hardware cache.  The TLB is associative, high speed memory.  Each entry in TLB consists of two parts: a tag and a value.  When this memory is used, then an item is compared with all tags simultaneously. If the item is found, then corresponding value is returned. Fig. 10.20: paging with offset Main memory access time = m If page table are kept in main memory, Effective access time = m (for page table) + m (for particular page in page table) CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 203 Fig. 10.21: Effective access Time calculation 10.8 Segmentation with Paging Segmentation is a memory management technique in which each job is divided into several segments of different sizes, one for each module that contains pieces that perform related functions. Each segment is actually a different logical address space of the program. When a process is to be executed, its corresponding segmentation are loaded into non- contiguous memory though every segment is loaded into a contiguous block of available memory. Segmentation memory management works very similar to paging but here segments are of variable-length where as in paging pages are of fixed size. 0 Main Program 0 Subroutine A 0 Subroutine B 99 Segment 2 199 Segment 1 349 Segment 0 Fig. 10.22: Segmented Memory Allocation Segmented memory allocation. Job 1 includes a main program, subroutine A, and subroutine B, so it’s divided into three segments. CU IDOL SELF LEARNING MATERIAL (SLM)

204 System Programming and Operating System 0 Main Program Segment Map Table Job 1 Memory 0 Segment no Size Status1 Access2 address 349 0 Subroutine A 0 350 Y E 4000 7000 199 1 200 Y E 0 Subroutine B 99 2 100 N E Job 1 3000 4000 Main Program 7000 Subroutine A 1 Y = in memory Main Memory 2 N = not in memory Fig. 10.23: Segmentation and Segmap Table A program segment contains the program's main function, utility functions, data structures, and so on. The operating system maintains a segment map table shown in Fig. 10.24, or every process and a list of free memory blocks along with segment numbers, their size and corresponding memory locations in main memory. For each segment, the table stores the starting address of the segment and the length of the segment. A reference to a memory location includes a value that identifies a segment and an offset. The system maintains three tables: 1. The job table (as with static paging). 2. The segment Map table list details about each job (one for each job). 3. Memory Map Table (as before). CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 205 Fig. 10.24: Segmentation The addressing scheme requires the segment number and the displacement within that segment, and, because the segments are of different sizes, the displacement must be verified to make sure it isn't outside of the segment's range. A segmented address reference requires the following steps: 1. extract the segment number and the displacement from the logical address. 2. use the segment number to index the segment table, to obtain the segment base address and length. 3. Check that the offset is not greater than the given length; if so an invalid address is signalled. 4. generate the required physical address by adding the offset to the base address. CU IDOL SELF LEARNING MATERIAL (SLM)

206 System Programming and Operating System Fig. 10.25: Address Mapping Main Points:  The benefits of segmentation include modularity of programs and sharing and protection.  There is a maximum segment size that the programmer must be aware of no internal fragmentation.  Unequal sized segments.  Non-contiguous memory. Some external fragmentation. Segmentation greatly facilitates the sharing of procedures or data between a number of processes. Because a segment normally has either program code or data within them different segments within the same process can have different protections set for them. While protection is possible in a paging environment it is far more difficult to implement, the programmer is unaware of what pages hold a procedure or data area that he may wish to share, to do this the programmer would have to keep track of the exact pages that held a procedure and then assign the necessary protection to those pages. 10.8.1 Difference between Paging and Segmentation No. Paging Segmentation 1. A page is a contiguous range of memory A segment is an independent address space. addresses which is mapped to physical Each segment has addresses in a range from 0 to memory. maximum value. CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 207 2. It has only one linear address space. It has many address spaces. 3. Programmer does not know that it is Programmer knows that it is implemented. implemented Procedures and data can be separated 4. Procedures and data cannot be separated Procedures can be shared between users 5. Procedures cannot be shared between users Procedures and data can be protected separately 6. Procedures and data cannot be protected Compilation can be done separately separately A segment is a logical unit 7. Compilation cannot be done separately A segment is of arbitrary size. 8. A page is a physical unit 9. A page is of fixed size 10.9 Summary Paging: A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard that's set up to emulate the computer's RAM. Paging technique plays an important role in implementing virtual memory. Paging is a memory management technique in which process address space is broken into blocks of the same size called pages (size is power of 2, between 512 bytes and 8192 bytes). The size of the process is measured in the number of pages. Inverted Page table: Inverted Page Table is the global page table which is maintained by the Operating System for all the processes. In inverted page table, the number of entries is equal to the number of frames in the main memory. It can be used to overcome the drawbacks of page table. There is always a space reserved for the page regardless of the fact that whether it is present in the main memory or not. However, this is simply the wastage of the memory if the page is not present. We can save this wastage by just inverting the page table. We can save the details only for the pages which are present in the main memory. Frames are the indices and the information saved inside the block will be Process ID and page number. CU IDOL SELF LEARNING MATERIAL (SLM)

208 System Programming and Operating System Page Replacement Algorithm: The page replacement algorithm decides which memory page is to be replaced. The process of replacement is sometimes called swap out or write to disk. Page replacement is done when the requested page is not found in the main memory (page fault). When total memory requirement in demand paging exceed the physical memory, then there is need to replace pages from memory to free frames for new pages. For replacement of pages various techniques are used. (a) FIFO Page Replacement (b) Optimal Page Replacement (c) LRU Page Replacement (d) NRU Not recently used (e) Clock Page Replacement Algorithm With computers, page size refers to the size of a page, which is a block of stored memory. Page size affects the amount of memory needed and space used when running programs. Most operating systems allow for the determination of the page size when a program begins running, which allows it to calculate the most efficient use of memory while running that program. Segmented Paging: Pure segmentation is not very popular and not being used in many of the operating systems. However, Segmentation can be combined with Paging to get the best features out of both the techniques. In Segmented Paging, the main memory is divided into variable size segments which are further divided into fixed size pages. 1. Pages are smaller than segments. 2. Each Segment has a page table which means every program has multiple page tables. 3. The logical address is represented as Segment Number (base address), Page number and page offset. 10.10 Key Words/Abbreviations  Segment Number: It points to the appropriate Segment Number.  Page Number: It Points to the exact page within the segment. CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 209  Page Offset: Used as an offset within the page frame. Each Page table contains the various information about every page of the segment. The Segment Table contains the information about every segment. Each segment table entry points to a page table entry and every page table entry is mapped to one of the page within a segment.  Page Table: A Page Table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual address and physical addresses. Virtual address is also known as Logical address and is generated by the CPU. While Physical address is the address that actually exists on memory. 10.11 Learning Activity 1. What do you mean by local replacement and global replacement? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 10.12 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Explain Inverted page tables. 2. Write note on page replacement algorithms. 3. What is page fault handling? 4. Explain working set model. 5. Explain local vs. global allocation. 6. Write note on page size. 7. Explain segmentation with paging. CU IDOL SELF LEARNING MATERIAL (SLM)

210 System Programming and Operating System B. Multiple Choice/Objective Type Questions 1. Inverted Page tables are sorted in order of __________ number (a) page (b) alogorithm (c) frame (d) table 2. The _________ page algorithm simply says that the page with the highest label should be removed. (a) optimal (b) replacement (c) FIFO (d) LRU 3. __________ is total demand exceeds the number of frames. (a) D < m (b) D >= m (c) D <= m (d) D > m 4. No pages are swapped in for a process until they are requested by page faults. This is known as pure __________. (a) LRU (b) demand paging (c) FIFO algorithm (d) page replacement 5. __________ is a memory management scheme that eliminates the need for contiguous allocation of physical memory. (a) Paging (b) Page size (c) Indexing (d) Virtual Answers 1. (c), 2. (a), 3. (d), 4. (b), 5. (a) 10.13 References Reference Books 1. http://web.eecs.umich.edu/~aprakash/482/notes/memory2.pdf 2. http://courses.mpi-sws.org/os-ss11/lectures/mem3.pdf 3. https://www.cl.cam.ac.uk/teaching/1516/OpSystems/pdf/07-Segmentation.pdf CU IDOL SELF LEARNING MATERIAL (SLM)

Memory Management - 2 211 Web Resources 1. https://www.tutorialspoint.com/operating_system/os_memory_management.htm 2. https://www.javatpoint.com/os-page-replacement-algorithms 3. https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/ 4. https://www.memorymanagement.org/mmref/begin.html CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 11 FILE SYSTEMS Structure: 11.0 Learning Objectives 11.1 Introduction 11.2 Concept 11.3 Access Methods 11.4 File System Structure 11.5 Directory Structure 11.6 Allocation Methods 11.7 Free Space Management 11.8 File Sharing 11.9 Protection and Recovery 11.10 Summary 11.11 Key Words/Abbreviations 11.12 Learning Activity 11.13 Unit End Questions (MCQ and Descriptive) 11.14 References

File Systems 213 11.0 Learning Objectives After studying this unit, you should be able to:  Explain about the File Systems.  Discuss about the File Structure and access Methods.  Explain about various Protection and Recovery Techniques. 11.1 Introduction A file can be “free formed”, indexed or structured collection of related bytes having meaning only to the one who created it. Or in other words an entry in a directory is the file. The file may have attributes like name, creator, date, type, permissions etc. A file consists of a collection of records. The way in which these records may be accessed determines its logical organization, and to some extent its physical Organization on disk. If a file is primary to be processed as a whole, then a sequential file organization is the simplest and most appropriate. If sequential access is needed but random access to individual file is also desired, then an indexed sequential file may give better performance. If access to the file is principally at random, then an indexed file may be the most appropriate. 11.2 Concept A file can be described as a container that stores data that is accessible by a computer system – it is basically a container holding a set of related information that will be stored on some form of secondary storage. A data file may consist of for example, a set of computer program instructions, text or another form of data. A text file may contain just a short letter, or contain a complete book. In other words a file is basically a defined set of named data. A file is a named collection of related information that is recorded on secondary storage. Also, a file is the smallest allotment of logical secondary storage; that is, data cannot be written to secondary storage unless they are within a file. CU IDOL SELF LEARNING MATERIAL (SLM)

214 System Programming and Operating System Information may be stored in are:  file-source programs,  object programs,  executable programs,  numeric data,  text,  payroll records,  graphic images,  Sound recordings. 11.3 Access Methods Purpose of file is to store information. This information must be accessed and read into computer memory. The information in the file can be accessed in several ways. Some systems provide only one access method for files and some provide many methods of access. For example IBM support many access methods, but the problem is selection of the right method for a particular application. Different access methods are  Sequential access method  Direct access method  Indexed access method Sequential Access Method The simplest access method is sequential access. Information in the file is processed in order, one record after the other. This mode of access is the most common method; for example, editors and compilers usually access files in this fashion. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 215 beginning current record end of title next record rewind read/write Fig. 11.1: Sequential Access The bulk of the operations on a file is reads and writes. A read operation reads the next portion (data) of the file and automatically advances a file pointer, which tracks the I/O location. Similarly, a write appends to the end of the file and advances to the end of the newly written material (the new end of file). Such a file can be reset to the beginning and, on some systems, a program may be able to skip forward or backward n records, for some integer n-perhaps only for n = 1. Sequential access is depicted in Fig. 11.1. Sequential access is based on a tape model of a file, and works as well on sequential-access devices as it does on random-access ones. Roll No. Name Address Age 123 Manoj Shd 24 124 Kaushal Unr 12 125 Rishabh Kyn 10 126 Asha Dom 22 127 Vimla Unr 60 Fig. 11.2: Sequential Access In this type of file a fixed format is used for records as shown in Fig. 11.2. All records are of the same length consisting of the same number of fixed length fields in a particular order. One particular field usually the first field in each record is referred to as the key field. The key field uniquely identifies the record. Advantages 1. Organization of data is in simple way 2. Easy to access the next record. CU IDOL SELF LEARNING MATERIAL (SLM)

216 System Programming and Operating System 3. Data structures are absent. 4. Sequential files are typically used in batch applications where they are involved in the processing of all the records such as payroll, billing etc. 5. They are easily stored on tapes as well as disks. 6. Automatic creation of backup. Disadvantages 1. Wastage of memory space because of master file and transaction file. For interactive applications that involve queries and/or updates of individual records, the sequential file provides poor performance. Direct Access (Relative Access) A file is made up of fixed length logical records that allow programs to read and write records in without a particular order. The direct-access method is based on a disk model of a file, since disks allow random access to any file block. For direct access, the file is seen as a numbered sequence of blocks or records. A direct- access file allows arbitrary blocks to be read or written. Thus, we may read block 24, then read block 13, and then write block 17. Shown in Fig. 11.3. Fig. 11.3: Direct Access CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 217 For the direct-access method, the file operations must be modified to include the block number as a parameter. Thus, we have read n, where n is the block number, rather than read next, and write n rather than write next. An alternative approach is to retain read next and write next, as with sequential access, and to add an operation position file to n, where n is the block number. Then, to effect a read n, we would position to n and then read next. Given a logical record length L, a request for record N is turned into an I/O request for L bytes starting at location L * (N – 1) within the file (assuming first record is N = 1). Since logical records are of a fixed size, it is also easy to read, write, or delete a record. Indexed Access Method These methods generally involve the construction of an index for the file. The index, similar to an index in the back of a book, contains pointers to the various blocks. To find a record in the file, user has to first search the index, and then use the pointer to access the file directly and to find the desired record. First Name Logical Record Manoj Number Kaushal Rishabh Asha Manager 37 KYN Asha Vimla Fig. 11.4: Indexed Access For example, IBM’s indexed sequential-access method (ISAM) uses a small master index that points to disk blocks of a secondary index. The secondary index blocks point to the actual file blocks. The file is kept sorted on a defined key. To find a particular item, we first make a binary search of the master index, which provides the block number of the secondary index. This block CU IDOL SELF LEARNING MATERIAL (SLM)

218 System Programming and Operating System is read in, and again a binary search is used to find the block containing the desired record. Finally, this block is searched sequentially. In this way, any record can be located from its key by at most two direct access reads. Fig. 11.4 shows a similar situation as implemented by VMS index and relative files. Advantages: 1. Variable length records are allowed. 2. Indexed sequential file may be updated in sequential or random mode. 3. Very fast operation. Disadvantages: 1. The major disadvantage of the indexed sequential file is that, as the file grows a performance deteriorates rapidly because of overflows and consequently there arises the need for periodic reorganization. Reorganization is an expensive process and the file becomes unavailable during reorganization. 2. When a new record is added to the main file. all of the Index files must be updated. Consumes large memory space for maintaining index files. 11.4 File System Structure A file has a certain defined structure according to its type. For example 1. A text file is a sequence of characters organized into lines (and possibly pages). 2. A source file is a sequence of subroutines and functions, each of which is further organized as declarations followed by executable statements. 3. An object file is a sequence of bytes organized into blocks understandable by the system’s linker. 4. An executable file is a series of code sections that the loader can bring into memory and execute. 5. When operating system defines different file structures, it also contains the code to support these file structure. Unix, MS-DOS support minimum number of file structure. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 219 The three common possibilities are as follows: 1. Stream of Bytes 2. Records 3. Tree Stream of Bytes For operating system regard files is just sequences of bytes and provides the maximum amount of flexibility. User programs can put any type of data they want in their files and accordingly. All versions of UNIX (including Linux and OS X) and Windows use this file model. The main advantage of such file structuring is that it simplifies file management for the operating system and Applications can have their own structure. 1 Byte 1 Record (a) Byte (b) Record Sequence Sequence Fig. 11.5: (a) Byte Sequence (b) Record Sequence CU IDOL SELF LEARNING MATERIAL (SLM)

220 System Programming and Operating System Fig. 11.6: Types of File Structure Record File Structure A file is a sequence of fixed length record, each with some Internal structure shown in Fig. 11.6. Collection of bytes is treated as a unit. For example employee record. Operations are at the level of records (read_record, write_record). File is a collection of similar records. Operating System can optimize operations on records. No current general-purpose system uses this model as its primary file system any more, but back in the days of 80-column punched cards and 132- character line printer paper this was a common model on mainframe computers. Tree File Structure In this organization, a file consists of a tree of records, not necessarily all the same length, each containing a key field in a fixed position in the record. The tree is sorted on the key field, to allow rapid searching for a particular key. The basic operation here is not to get the __next‘‘ record, although that is also possible, but to get the record with a specific key. The system can search a file with key without worrying about its exact position in the file. Also, new records can be added to the file, with the operating system, and not the user, deciding where to place them. This type of file is clearly quite different from the unstructured byte streams used in UNIX and Windows and is used on some large mainframe computers for commercial data processing. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 221 11.5 Directory Structure The file systems of computers can be extensive. Some systems store Megabytes of files on terabytes of disk. To manage all these data, we need to organize them. When there are many file searching time increases hence in order to save that time organization of data can be done on disk. Directory structure Organizes and provides Fig. 11.7: Directory Structure This organization is usually done in two parts. 1. Disks are split into one or more partitions, also known as minidisks in the IBM world or volumes in the PC and Macintosh. Each disk on a system contains at least one partition, which is a low-level structure in which files and directories reside. Di sk Fig. 11.8: File system About Partitions and Volume: (a) Partitions are used to provide several separate areas within one disk, each treated as a separate storage device, whereas other systems allow partitions to be larger than a disk to group disks into one logical structure. CU IDOL SELF LEARNING MATERIAL (SLM)

222 System Programming and Operating System (b) Hence the user needs to be concerned with only the logical directory and file structure, and can ignore completely the problems of physically allocating space for files. Hence for this reason partitions can be thought of as virtual disks. (c) Partitions can also store multiple operating systems, allowing a system to boot and run more than one. 2. Each partition contains information about files within it. This information is kept in entries in a device directory or volume table of contents. The device directory (more commonly known simply as a directory) records information – such as name, location, size, and type – for all files on that partition. Figure shows the typical file-system organization. The directory can be viewed as a symbol table that translates file names into their directory entries. If we take such a view, we see that the directory itself can be organized in many ways. The most common schemes for defining the logical structure of a directory.  Single Level Directory  Two-Level Directory  Tree Directory Structure  Single Level Directory: The simplest directory structure is the single-level directory. All files are contained in the same directory, which is easy to support and understand shown in Fig. 11.8. A single-level directory has significant limitations, however, when the number of files increases or when the system has more than one user. Since all files are in the same directory, they must have unique names. If two users call their data file test, then the unique-name rule is violated. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 223 Single Level Directory All files are contained in the same directory. Limitations (Naming problem, Grouping problem) Fig. 11.9: Single Level Directory Structure For example, in one programming class, 23 students called the program for their second assignment prog 2; another 11 called it assign 2. Although file names are generally selected to reflect the content of the file, they are often limited in length. The MS-DOS operating system allows only 11-character file names; UNIX allows 255 characters. Even a single user on a single-level directory may find it difficult to remember the names of all the files, as the number of files increases. It is not uncommon for a user to have hundreds of files on one computer system and an equal number of additional files on another system. A single-level directory often leads to confusion of file names between different users. The standard solution is to create a separate directory for each user.  Two Level Directory Structure In the two-level directory structure, each user has her own User File Directory (UFD). Each UFD has a similar structure, but lists only the files of a single user. When a user job starts or a user logs in, the system’s Master File Directory (MFD) is searched. The MFD is indexed by user name or account number, and each entry points to the UFD for that user. When a user refers to a particular file, only his own UFD is searched. Thus, CU IDOL SELF LEARNING MATERIAL (SLM)

224 System Programming and Operating System different users may have files with the same name, as long as all the file names within each UFD are unique. Two Level Directory ■ Efficient searching ■ No grouping capability ■ Separate directory for each user ■ Can have the same file name for different user master file directory user file directory Fig. 11.10: Two Level Directory Structure To create a file for a user, the operating system searches only that user’s UFD to ascertain whether another file of that name exists. To delete a file, the operating system confines its search to the local UFD; thus, it cannot accidentally delete another user’s file that has the same name. Fig. 11.10. Shows Two level File Structure. The user directories themselves must be created and deleted as necessary. A special system program is run with the appropriate user name and account information. The program creates a new UFD and adds an entry for it to the MFD. The execution of this program might be restricted to system administrators.  Hierarchical /Tree Directory Tree directory structure is the most popular tree structure. It is very useful because it solves the problem of grouping. i.e. it can group different users or directories. Again the data can be efficiently searched due to path concept. Path describes where exactly that file or directory is store. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 225 Tree Structured Directories  Subdirectories  Efficient searching  Grouping Capability  Current directory (working directory) Fig. 11.11: Tree Directory In the tree-structured directory, the directory themselves are files. This leads to the possibility of having sub-directories that can contain files and sub-subdirectories shown in Fig. 11.11. An interesting policy decision in a tree-structured directory structure is how to handle the deletion of a directory. If a directory is empty, its entry in its containing directory can simply be deleted. However, suppose the directory to be deleted id not empty, but contains several files, or possibly sub-directories. Some systems will not delete a directory unless it is empty. Thus, to delete a directory, someone must first delete all the files in that directory. If these are any sub-directories, this procedure must be applied recursively to them, so that they can be deleted also. This approach may result in a insubstantial amount of work. An alternative approach is just to assume that, when a request is made to delete a directory, all of that directory’s files and sub-directories are also to be deleted. The Microsoft Windows family of operating systems (95,95, NT, 2000) maintains an extended two-level directory structure, with devices and partitions assigned a drive letter. CU IDOL SELF LEARNING MATERIAL (SLM)

226 System Programming and Operating System  Acyclic-Graph Directories: Fig. 11.12: Acyclic Directory Structure The acyclic directory structure shown in Fig. 11.12. is an extension of the tree-structured directory structure. In the tree-structured directory, files and directories starting from some fixed directory are owned by one particular user. In the acyclic structure, this prohibition is taken out and thus a directory or file under directory can be owned by several users.  Path Name A path, the general form of the name of a file or directory, specifies a unique location in a file system. A path points to a file system location by following the directory tree hierarchy expressed in a string of characters in which path components, separated by a delimiting character, represent each directory. The delimiting character is most commonly the slash (“/”), the backslash character (“\\”), or colon (“:”), though some operating systems may use a different delimiter. Paths are used extensively in computer science to represent the directory/file relationships common in modern operating systems, and are essential in the construction of Uniform Resource Locators (URLs). Resources can be represented by either absolute or relative paths. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 227 11.6 Allocation Methods Contiguous Allocation Fig. 11.13: Contiguous File Allocation Methods Contiguous Allocation Fig. 11.14: Contiguous File Allocation CU IDOL SELF LEARNING MATERIAL (SLM)

228 System Programming and Operating System The contiguous allocation method requires each file to occupy a set of contiguous address on the disk. Disk addresses define a linear ordering on the disk. Notice that, with this ordering, accessing block b+1 after block b normally requires no head movement. When head movement is needed (from the last sector of one cylinder to the first sector of the next cylinder), it is only one track. Thus, the number of disk seeks required for accessing contiguous allocated files in minimal, as is seek time when a seek is finally needed. Contiguous allocation of a file is defined by the disk address and the length of the first block. If the file is n blocks long, and starts at location b, then it occupies blocks b, b + 1, b + 2, …, b + n – 1. The directory entry for each file indicates the address of the starting block and the length of the area allocated for this file. Fig. 11.13 and Fig. 11.14 show contiguous File allocation method. Advantages of Contiguous Allocation 1. Supports both sequential and direct access methods. 2. Contiguous allocation is the best form u allocation for sequential files. Multiple blocks can be brought in at a time to Improve I/O performance for sequential processing. 3. It is also easy to retrieve a single block from a file. For example if a file starts at block n and the 1 block of the me is wanted, its location on secondary storage is simply n + i. 4. Quick and easy calculation of block holding data - just offset from start of file. 5. For sequential access, almost no seeks required. 6. Even direct access is fast - just seek and read only one disk access. Disadvantages of contiguous file system are as follows: 1. There is no best place to put a new file. 2. Problems when file gets bigger - may have to move whole file. 3. External Fragmentation. 4. Compaction may be required, and it can be very expensive. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 229 Linked Allocation Fig. 11.15: Linked File Allocation Fig. 11.16: Linked File Allocation In linked allocation shown in Fig. 11.15., each file is a linked list of disk blocks. The directory contains a pointer to the first and (optionally the last) block of the file. For example, a file of 5 blocks which starts at block 4, might continue at block 7, then block 16, block 10, and CU IDOL SELF LEARNING MATERIAL (SLM)

230 System Programming and Operating System finally block 27. Each block contains a pointer to the next block and the last block contains a NIL pointer. The value -1 may be used for NIL to differentiate it from block 0. With linked allocation, each directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a file removes the first free block and writes to that block. This new block is then linked to the end of the file. To read a file, the pointers are just followed from block to block. Advantages of Linked Allocation 1. Does not suffer from external fragmentation. 2. Support both sequential and direct access to the file. 3. No more variable-sized file allocation problems. Everything takes place in fixed-size chunks, which makes memory allocation a lot easier. 4. No more external fragmentation. 5. No need to compact or relocate files. Disadvantages of Linked Allocation 1. Potentially terrible performance for direct access files - have to follow pointers from one disk block to the next! 2. Even sequential access is less efficient than for contiguous files because may generate long seeks between blocks. 3. Reliability -if loses one pointer, have big problems. Linked with Memory table / Indexed Allocation The indexed allocation method is the solution to the problem of both contiguous and linked allocation. This is done by bringing all the pointers together into one location called the index block. Of course, the index block will occupy some space and thus could be considered as an overhead of the method. In indexed allocation, each file has its own index block, which is an array of disk sector of addresses. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 231 Fig. 11.17(a): Indexed Allocation Fig. 11.17(b): Indexed Allocation Fig.11.17(a) and Fig.11.17(b) shows indexed File Allocation. With entry in the index block points to the ith sector of the file. The directory contains the address of the index block of a file. CU IDOL SELF LEARNING MATERIAL (SLM)

232 System Programming and Operating System To read the ith sector of the file, the pointer in the ith index block entry is read to find the desired sector. Indexed allocation supports direct access, without suffering from external fragmentation. Any free block anywhere on the disk may satisfy a request for more space. I-Node Allocation For keeping track of which blocks belong to which file is to associate with each file a data structure called an i-node (index-node), which lists the attributes and disk addresses of the file‘s blocks. A simple example is shown in Fig. 11.18. Given the i-node, it is then possible to find all the blocks of the file. The main advantage of this scheme over linked files using an in-memory table is that the i-node need be in memory only when the corresponding file is open. If each i-node occupies n bytes and a maximum of k files may be open at once, the total memory occupied by the array holding the i-nodes for the open files is only kn bytes. But this space need be reserved in advance. File Attributes Address of disk block 0 Address of disk block 1 Address of disk block 2 Address of disk block 3 Address of disk block 4 Address of disk block 5 Address of disk block 6 Address of disk block 7 Address of block of pointers Disk block containing additional disk address Fig. 11.18: I-Node File Allocation CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 233 This array occupies less memory or space then file table. The table for holding the linked list of all disk blocks is proportional in size to the disk itself. If the disk has n blocks, the table needs n entries. As disks grow larger, this table grows linearly with them. But, the i-node scheme requires an array in memory whose size is proportional to the maximum number of files that may be open at once. It does not matter if the disk is 100 GB to 10,000 GB. One problem with i-nodes is that if each one has room for a fixed number of disk addresses, what happens when a file grows beyond this limit? One solution is to reserve the last disk address not for a data block, but instead for the address of a block containing more disk-block addresses, as shown in Fig. 11.18. Even more advanced would be two or more such blocks containing disk addresses or even disk blocks pointing to other disk blocks full of addresses. Implementation of Directory The operating system uses the path name supplied by the user to locate the directory entry on the disk. The directory entry provides the information needed to find the disk blocks. File can be located on the disk using the method discussed above. In all cases, the main function of the directory system is to map the ASCII name of the file onto the information needed to locate the data. games attributes games mail attributes mail news attributes news work attributes work (a) (b) Data structure containing the attributes Fig. 11.19 Fig. 11.19(a) A simple directory containing fixed-sized entries with the disk addresses and attributes in the directory entry. (b) A directory in which each entry just refers to an I-node. CU IDOL SELF LEARNING MATERIAL (SLM)

234 System Programming and Operating System The attributes of file system are generally stored with directory entry as shown in Fig. 20(a). following are different ways of implementing  In this simple design, a directory consists of a list of fixed-size entries, one per file, containing a (fixed-length) file name, a structure of the file attributes,  One or more disk addresses (up to some maximum) telling where the disk blocks are.  For systems that use i-nodes, another possibility for storing the attributes is in the i-nodes, rather than in the directory entries.  In that case, the directory entry can be shorter: just a file name and an i-node number. This approach is illustrated in Fig. 20(b). File 1 entry length Pointer to file 1’s name Entry File 1 attributes for one File 1 attributes Pointer to file 2’s name file pro j File 2 attributes Entry ec t - for one bu dg Pointer to file 3’s name et File 3 attributes file File 2 entry length pro j File 2 attributes ect per s onn e budg l et p File 3 entry length e r so Heap File 3 attributes f oo nne l f oo (a) (b) Fig. 11.20: Two ways of handling long file names in a directory. (a) In-line. (b) In a Heap. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 235 Fixed Length File Name Generally files have short, fixed-length names. In MS-DOS files have a 1–8 character base name and an optional extension of 1–3 characters. In UNIX Version 7, file names were 1–14 characters, including any extensions. But all modern operating systems support longer, variable- length file names. Variable Length File Name The simplest approach is to set a limit on file-name length, typically 255 characters, and then use one of the designs of Fig. 11.20 with 255 characters reserved for each file name. This approach is simple, but wastes a great deal of directory space, since few files have such long names. Another way is that all directory entries are the same size. Here, each directory entry contains a fixed portion, typically starting with the length of the entry, and then followed by data with a fixed format, usually including the owner, creation time, protection information, and other attributes. A disadvantage of this method is that when a file is removed, a variable-sized gap is introduced into the directory into which the next file to be entered may not fit. Another way to handle variable-length names is to make the directory entries themselves all fixed length and keep the file names together in a heap at the end of the directory, as shown in Fig. 11.20(b). This method has the advantage that when an entry is removed, the next file entered will always fit there. Of course, the heap must be managed and page faults can still occur while processing file names. 11.7 Free Space Management In free space management techniques mainly two methods are used as follows: 1. Bitmap 2. Linked List 3. Grouping 4. Counting CU IDOL SELF LEARNING MATERIAL (SLM)

236 System Programming and Operating System Bitmap Technique Frequently, the free-space list is implemented as a bitmap or bit vector shown in Fig. 11.21. Each block is represented by a 1 bit. If the block is free, the bit is 0; if the block is allocated, the bit is 1. For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, and 27 are free, and the rest of the blocks are allocated. The free-space bitmap would be: Blocks 0 1 2 3 4 5 6 7 8 9 10 11 12 13 00 1 1 1 1 00 1 11 1 0 0 bits Fig. 11.21: Bitmap Advantages with Bitmap Technique The main advantage of this approach is that it is relatively simple and efficient to find n consecutive free blocks on the disk. Unfortunately, bit vectors are inefficient unless the entire vector is kept in memory for most accesses. Keeping it main memory is possible for smaller disks such as on microcomputers, but not for larger ones. Problem with Bitmap Technique There is one problem associated with bitmap that when k unit processes runs in the memory, the memory manager has to search a ‗0‘ bitmap which are consecutive ‗n‘ units. The main argument against bitmap is that the searching a bitmap for a run of a given length is a slow operation. Linked Lists Technique Linked list is another way using which track of free and used memory can be tracked. Link list is collection of allocated memory or hole between two processes. As shown in figure P indicates the process and H indicates the hole (free memory). All the entries present in the list specifies a hole (H) process (P) and address at which it starts, the length and a pointer to the next entry. CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 237 From the example shown in Fig. 11.22. This list is always kept sorted. One of the major advantages of sorting is that when a process terminates or when a process terminates or when a process is swapped out the updating list is straight forward. Fig. 11.22: Linked Free Space Management A terminating memory has two neighbours only. In exceptional cases like when it is at the top of the memory and at the bottom of the memory. At the top of the memory it do not have neighbour at the left side At the bottom of the memory there is no neighbour at the right side. The neighbours could be holes or process. free-space list head Fig. 11.23 CU IDOL SELF LEARNING MATERIAL (SLM)

238 System Programming and Operating System There could be for combinations as shown in the Fig. 11.22(a) shows modifying the list requires replacing a P by H. Fig. 11.22 (b) and (c) also two entries and combined into one and the list becomes one entry shorter. Doubly link list is useful to find out most recent entry and to see if merge is possible. When processes or even holes are kept sorted in the list, and then different algorithms could be used to allocate the memory. These algorithm are called as (i) First Fit (ii) Best Fit (iii) Next Fit (iv) Worst Fit Grouping A modification of the free-list approach is to store the addresses of n free blocks in the first free block. The first n-1 of these is actually free. The last one is the disk address of another block containing addresses of another n free blocks. The importance of this implementation is that addresses of a large number of free blocks can be found quickly. Counting Another approach is to take advantage of the fact that, generally, several contiguous blocks may be allocated or freed simultaneously, particularly when contiguous allocation is used. Thus, rather than keeping a list of free disk addresses, the address of the first free block is kept and the number n of free contiguous blocks that follow the first block. Each entry in the free-space list then consists of a disk address and a count. Although each entry requires more space than would a simple disk address, the overall list will be shorter, as long as the count is generally greater than 1. 11.8 File Sharing File sharing is the public or private sharing of computer data or space in a network with various levels of access privilege. While files can easily be shared outside a network (for example, simply by handing or mailing someone your file on a diskette), the term file sharing almost CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 239 always means sharing files in a network, even if in a small local area network. File sharing allows a number of people to use the same file or file by some combination of being able to read or view it, write to or modify it, copy it, or print it. Typically, a file sharing system has one or more administrators. Users may all have the same or may have different levels of access privilege. File sharing can also mean having an allocated amount of personal file storage in a common file system. File sharing has been a feature of mainframe and multi-user computer systems for many years. With the advent of the Internet, a file transfer system called the File Transfer Protocol (FTP) has become widely-used. FTP can be used to access (read and possibly write to) files shared among a particular set of users with a password to gain access to files shared from an FTP server site. Many FTP sites offer public file sharing or at least the ability to view or copy files by downloading them, using a public password (which happens to be “anonymous”). Most Website developers use FTP to upload new or revised Web files to a Web server, and indeed the World Wide Web itself can be thought of as large-scale file sharing in which requested pages or files are constantly being downloaded or copied down to the Web user. File sharing can be done using several methods. The most common techniques for file storage, distribution and transmission include the following:  Removable storage devices  Centralized file hosting server installations on networks  World Wide Web-oriented hyperlinked documents  Distributed peer-to-peer networks Operating systems also provide file-sharing methods, such as network file sharing (NFS). Most file-sharing tasks use two basic sets of network criteria, as follows:  Peer-to-Peer (P2P) File Sharing: This is the most popular, but controversial, method of file sharing because of the use of peer-to-peer software. Network computer users locate shared data with third-party software. P2P file sharing allows users to directly access, CU IDOL SELF LEARNING MATERIAL (SLM)

240 System Programming and Operating System download and edit files. Some third-party software facilitates P2P sharing by collecting and segmenting large files into smaller pieces.  File Hosting Services: This P2P file-sharing alternative provides a broad selection of popular online material. These services are quite often used with Internet collaboration methods, including email, blogs, forums, or other mediums, where direct download links from the file hosting services can be included. These service websites usually host files to enable users to download them. 11.9 Protection and Recovery File protection: Preventing accidental erasing of data. Physical file protection is provided on the storage medium by turning a switch, moving a lever or covering a notch. Writing is prohibited even if the software directs the computer to do so. For example, on the earlier half-inch tape, a plastic ring in the center of the reel was removed (no ring-no write). Logical file protection is provided by the operating system, which can designate files as read only. This allows both regular (read/write) and read only files to be stored on the same disk volume. Files can also be designated as hidden files, which makes them invisible to most software programs. Need of Protection  To prevent the access of unauthorized users and  To ensure that each active programs or processes in the system uses resources only as the stated policy,  To improve reliability by detecting latent errors. Role of Protection The role of protection is to provide a mechanism that implement policies which defines the uses of resources in the computer system. Some policies are defined at the time of design of the CU IDOL SELF LEARNING MATERIAL (SLM)

File Systems 241 system, some are designed by management of the system and some are defined by the users of the system to protect their own files and programs. Every application has different policies for use of the resources and they may change over time so protection of the system is not only concern of the designer of the operating system. Application programmer should also design the protection mechanism to protect their system against misuse. Policy is different from mechanism. Mechanisms determine how something will be done and policies determine what will be done. Policies are changed over time and place to place. Separation of mechanism and policy is important for the flexibility of the system. File Recovery Retrieval of a deleted or damaged computer file. Modern operating systems do not automatically eradicate a deleted file but prompt for the user’s confirmation. Files so deleted may still be recoverable by some utility programs if the space occupied by the deleted file has not been occupied (overwritten) by another file. A damaged file can only be recovered if its data is not corrupted beyond a minimal degree. Recovery of data where the media itself has been damaged requires highly specialized equipment and techniques offered exclusively by data recovery service firms. File recovery is different from file restoration where a backup file stored in a compressed (encoded) form is restored to its usable (decoded) form. How files are stored on the disk An important article for file recovery from SSD devices: To understand how files can be recovered from a disk, it helps to understand how files are stored on hard disks before they are lost. Most modern operating systems divide (or “partition”) the entire physical hard drive into one or several independent parts (“partitions”). In the DOS/Windows-based OS families, these partitions are called “logical disks.” Logical disks are assigned drive letters and optional descriptive labels. For example, C: (System) or D: (Data). Each partition has its own file system type, independent from other partitions on the same physical disk. For example, a physical hard drive for a Windows system may contain two logical disks: one NTFS and another FAT32. CU IDOL SELF LEARNING MATERIAL (SLM)

242 System Programming and Operating System Information about the partitions on the disk is stored at the beginning of the hard drive. This is usually referred to as a “partition table” or “partition map.” A typical partition structure is shown in Fig. 11.24. Hard drive service Partition Partition Partition data and info about (logical disk) 1 (logical disk) 2 (logical disk) N partition structure Fig. 11.24: Hard drive structure The hard drive service data and info about partition structure portion shown in Fig. 11.24 is known as “meta-data.” That is, information about the data on the disk (as opposed to the data itself). Similarly, each partition or logical disk is divided into two parts: one stores information about the disk (folder structure, file system, etc.) and the other stores the data that comprises those files. This division of data from meta-data allows for better disk space management, faster file search and increased reliability. Fig. 11.25 shows a typical logical disk structure. Disk Info about files Data of Some info Data of Some info Info about files Un- Data of service and folder File 1 about files File 2 about files and folder allocated File N information Copy 1 and folder and folder Copy 2 space Info about the disk and file system Data of stored file Fig. 11.25: Logical disk structure The disk service information shown in Fig. 11.25 contains specific information about the partition size, file system type, etc. This is necessary for the computer to correctly find the necessary data on the partition. The info about files and folders contains file records that store filenames, sizes, date/times, and other technical information. This information also includes the exact physical locations (addresses) of the file data on the disk. This information is usually backed up on the drive itself, in case the first copy becomes corrupted. CU IDOL SELF LEARNING MATERIAL (SLM)