Computer Science 111 Problem Set 6: ----------------- Revised November 16, 2001 746 AM Due date: November 20, 2001 In this assignment, we will look at the basic ideas underlying the construction of a file system. The ideas here are extensions of what was discussed in lecture. The assignment is (hopefully) self-contained, everything you need to do to complete the assignment should be explained here. As you will recall from lecture, files are stored in non-volatile memory on a disk. Your files remain unchanged on the disk even if the computer to which they are connected is turned off. When you are using the computer, you can fetch files from the disk into main memory (RAM) and can operate on a file (eg if it is a text file, you can add text, Change text, delete text). When you save the file, it is copied from RAM to your disk for permanent storage. I passed around a disk in class and as you could see, it had 2 shiny plates on which information could be stored. The information is reduced to quite a small size. In current technology, one square inch on a disk platter can store 10 gigabits (or 1.25 gigabyte) of information. This is about 1450 average sized novels in an area only slightly larger than a postage stamp. Breakthroughs in hardware continue to be remarkable and more are expected in the years to come. In the past 6 years, the average data-storage capacity (which is measured in bytes per square inch) of disk drives has increased eighteenfold, while the price per megabyte has dropped fifty-twofold. We will assume in this assignment that this trend will continue in the future. While the breakthroughs in disk hardware technology are wonderful, they are only useful if we can make effective use of disks of larger capacity. We mentioned in class that disks are divided into blocks and a file might be stored across many blocks. In order to allow for fragmentation, the portions of the file might not be on contiguous blocks of the disk. For the rest of this assignment, assume that a disk is broken into blocks each of which can store a fixed amount of information (in practice, this is often 1 or 4 kilobytes of information). Each block has a unique number. These numbers start at 1 and go up. So, a file that contains a megabyte of data might be stored on 1024 blocks of 1 kilobyte each and these blocks might be numbered 1, 2, 3, ... 1024. Each block also contains the number of the block before it and the one after it in sequence. This is done to give us more flexibility as we'll see below. There is also a special block of the disk which is always the start block. We give this block number 0. It contains the number of the block after it and there is no block before it. It is very important that block 0 never be used for storage. It is just a marker that keeps track of things for us. Initially, block number N contains the information that it comes after N-1 and before N+1. However, as we will see below this changes. Imagine that we start with a disk of 11 blocks (10 are regular blocks numbered 1, 2, ..., 10) and one is the start block numbered 0. So, the block structure looks something like this. BLOCK NUMBER NEXT BLOCK PRIOR BLOCK 0 1 1 2 0 2 3 1 3 4 2 4 5 3 5 6 4 6 7 5 7 8 6 8 9 7 9 10 8 10 9 The special block 0 is the Master Block. It keeps track of which blocks on the disk are free. So, initially, the Master Block tells us that Block 1 is free and block 1 tells us that Block 2 is free, etc. We often draw this as [Block 0] ---> [Block 1] -> [Block 2] -> [Block 3] ... and refer to this as the ``free block list''. Suppose we create a file FILE1 and ask to store it on the disk. We note that it will require 2 blocks of storage. The file system looks at block 0 which says that the block after it is block 1 and block 1 says that the one after it is block 2. That is, Blocks 1 and 2 are the first 2 blocks on the free block list. Blocks 1 and 2 are then used to store FILE1. To make everything work, block 0 now records block 3 as the block after it, block 3 records block 0 as the block before it, block 1 records that there is no block before it and block 2 records that there is no block after it. So, our drawings might look like ``free block list'': [Block 0] ---> [Block 3] -> [Block 4] -> [Block 5] ... FILE1: [Block 1] ---> [Block 2] and our snapshot of the disk will change tot he picture BLOCK NUNMBER NEXT BLOCK PRIOR BLOCK 0 3 3 4 0 4 5 3 ..... 1 2 2 1 We also must record that FILE1 is 2 blocks long and starts at block number 1, we do so in another table FILE NAME FILE SIZE (in blocks) FIRST BLOCK FILE1 2 1 For each of the parts of problems 1 to 4, describe what happens in response to that operation and give a snapshot of the relevant part of the disk after that operation. Note that it is typically not allowed to move blocks of a file that is already on the disk. So, we cannot move FILE1 to make space to store FILE2, etc. Also, note that the blocks used to store a file do not need to occur in number order. We can use the information about NEXT and PRIOR blocks to enable us to trace the blocks used to store a file. Note that there is one list for each file giving the blocks (in order) used to store it. There is also a ``free block list''. When a file is created, the blocks needed for it come from the free block list. When a file is deleted, the blocks it used are returned to the free block list. 1. [Storing files] A) We now create FILE2 which requires 3 blocks. 2. [Editing files] A) Now, we edit FILE2 and need to add another block to store it. B) Next, we edit FILE1 and need to add another block to store it. 3. [Deleting files] A) Suppose the situation is as it was after Problem 1: FILE1 and FILE2 are both on disk, FILE1 is 2 blocks long, and FILE2 is 3 blocks long. Now we delete FILE2. B) Again, suppose the situation is as it was after Problem 1: FILE1 and FILE2 are both on disk, FILE1 is 2 blocks long, and FILE2 is 3 blocks long. This time we delete FILE1. 4. Suppose that we start with a clean disk and do the sequence of operations A) create FILE1 of 2 blocks B) create FILE2 of 3 blocks C) create FILE3 of 3 blocks D) delete FILE2 E) create FILE4 of 2 blocks F) delete FILE1 G) create FILE5 of 3 blocks Describe how the file system handles each of these operations. 5. A common operation done on a disk is to de-fragment the disk. When we do this, we scan the blocks of each file on the disk and put them in contiguous locations. This is a fairly tedious process as we have to track down each block of the file and move them together while keeping track of the blocks that they displace. For the situation after all the actions of problem 4 have been taken, show the steps that would be gone through to defragment the disk. Your method has to work step by step. At each step, you are able to switch the (data) contents of two blocks and then update the information they contain about LAST and NEXT BLOCKs.