Description
Notes: The project is must be done individually. You may discuss the problems with other students and post questions to the OS discussion forum but the submitted work must be your own work. This assignment is worth 20% of your total grade.
Corresponding TA: Fareed Qararyah (email: fqararyah18@ku.edu.tr)
Description
Allocating space e ciently is a main concern when designing a le system or a memory management system. The criteria to assess certain design is space utilization and I/O per-formance. The objective of this assignment is to understand, implement, and empirically measure the performance of two space allocation methods used in le systems, namely con-tiguous and linked allocation, against various inputs.
The following are the assumptions and limitations of the le system:
The le system consists of a single directory. The directory has a xed size of 32768 blocks.
The block size is xed for a single experiment, but might change from experiment to experiment as discussed later.
The directory has a Directory Table (DT). An entry in DT consists of: le identi er, the index of the starting block of the le and the le size.
Linked allocation should be implemented using File-Allocation Table (FAT).
There is no extra space. However, we assume that there is su cient space to store the DT, and a xed 32768 blocks to store our data. In the linked allocation, part of this xed space will be used to keep the FAT.
Other than DT and FAT, you are not supposed to de ne any additional data structures. We assume you have a xed memory, e.g. a set of registers, su cient to store xed number of variables. In addition, you have a bu er of size equal to one block size, meaning that if you want to alter the location of a le, you can do it block by block.
A le can occupy one or more blocks. A single block cannot be shared.
In contiguous allocation, we have three alternatives for hole allocation. You are sup-posed to implement rst t strategy.
1
COMP 304 ( Spring 2020): Project 3
Functionalities Space Allocation MethodsEXPERIMENTATION AND ANALYSIS
Functionalities
Your design is expected to provide a capability of serving four main requests:
create file(file id, file length) This function allocates a space for the le of size file length bytes on the disk, updates the DT and the FAT. The le blocks may be lled with random number greater than zero. A suitable hole need to be found in contiguous allocation case. If no whole is found, you need to do compaction/defrag-mentation of the directory contents. If there is not enough space to store the le, the operation will be rejected with a warning message.
access(file id, byte offset) Returns the location of the byte having the given o set in the directory, where byte offset is the o set of that byte from the beginning of the le.
extend(file id, extension) Extends the given le by the given amount, where extension is the number of blocks not bytes. For simplicity, the extension will always add block after the last block of the le. If there is no su cient space to extend the le, the operation will be rejected with a warning message. In contiguous allocation, if there is no contiguous space, you need to do compaction and may reallocate the le blocks. Remember that you have a bu er that can accommodate only single block.
shrink(file id, shrinking) Shrinks the le by the given number of blocks. The shrinking deallocates the last blocks of the le. Note that deallocation means just that these blocks are no more referred by that le and you can use them to store new data, and there is no need to move them or the les adjacent to them at the moment. You can indicate that block is freed by storing zero in it, knowing that you store random positive values in the lled blocks.
These requests are simpli ed abstractions of the manipulations in a le system. When a le is created or extended you may ll the newly allocated space with a random number greater than zero. When a block is deallocated you may ll it with zero. Since we are not requesting a write operation on a certain o set, you do not need to allocate block size for each block, you can just allocate a single integer random value. The block size will be needed just to do some calculation like the size of a le to be created, or an o set to be returned.
Note, the defragmentation is expected to be done in one direction. This direction is from high to low indices. This is to have consistent results. Under the given assumption and in certain scenarios, implementing defragmentation in a di erent way might a ect the extension rejection ratio and we need to avoid this.
Experimentation and Analysis
A main goal of this project is to be able to decide when to use which allocation strategy. You are provided with text les each of them contains a sequence of operations representing
Student Name: Page 2 of 4
COMP 304 ( Spring 2020): Project 3
Space Allocation Methods DELIVERABLES
system with certain allocation characteristics. You need to evaluate your design against these inputs. For each input you are expected to report:
The number of les that their creation is rejected. The number of les that their extension is rejected.
The average running time of an operation. For this you should run with each input 5 times and take the average.
For a certain input le, the block size is indicated after the ’input ’. For example a le named input 1024 150 5 5 0.txt has a block size of 1024. The input les contain an operation in each line:
Each line is colon-separated. A line ’c:bytes’ is a create call.
A line ’a: le id:o set’ is an access call.
A line ’e: le id:extension blocks’ is extension.
A line ’sh: le id:shrinking blocks’ is shrinking.
After reporting the experiment results, you need to answer the following questions:
With test instances having a block size of 1024, in which cases (inputs) contiguous allocation has a shorter average operation time? Why? What are the dominating operations in these cases? In which linked is better, why?(10 pt.)
Comparing the di erence between the creation rejection ratios with block size 2048 and 32, what can you conclude? How did dealing with smaller block sizes a ect the FAT memory utilization? (5 pt.)
FAT is a popular way to implement linked allocation strategy. This is because it permits faster access compared to the case where the pointer to the next block is stored as a part of the concerned block. Explain why this provides better space utilization. (5 pt.)
If you have extra memory available of a size equal to the size of the DT, how can this improve the performance of your defragmentation?(3 pt.)
How much, at minimum, extra memory do you need to guarantee reduction in the number of rejected extensions in the case of contiguous allocations? ( 3 pt.)
Deliverables
You are required to submit the followings packed in a zip le (named your-username(s).zip)
to blackboard :
Student Name: Page 3 of 4
COMP 304 ( Spring 2020): Project 3
Space Allocation Methods DELIVERABLES
You can implement your program using any of programming languages of C, C++, Java or Python. Upload your source. Upload your .c, .cpp, .java or .py les. Please comment your implementation, it helps getting higher marks if the results are incorrect.
The relative performance of your code matters in addition to the correctness of the results. If you implement one of the strategies poorly, it might produce slower average operation time in all cases.
A report brie y describing your implementation, particularly which parts of your code work, which parts do not work. Report should address the questions in the experiments and analysis.
Grading: Contiguous Allocation (37 pts= 7.5 pts for each functionality + 7 pts perfor-mance), Linked Allocation (37 pts= 7.5 pts for each functionality + 7 pts performance), Report and Answering Analysis Questions (26 pts)
GOOD LUCK.
Student Name: Page 4 of 4
