Assignment #10 – Part One and Tw0 Solution



What to submit: One zip file named <studentID> <studentID> with your own student ID). It should contain four files:

  • one PDF file namedhw10.pdffor Section 1.Write your answers inEnglish. Check your spelling and grammar. Include your name and studentID!

  • The programming assignment will be posted separately with its own duedate.

  1. [30 points] ProblemSet

    1. [20 points]11.2Contrast the performance of the three techniques for allocating disk blocks (contiguous, linked, and indexed) for both sequential and random file access.You must elaborate to receive fullcredit.

    1. [10 points]11.8Consider a file system that uses inodes to represent files. Disk blocks are 8 KB in size, and a pointer to a disk block requires 4 bytes. This file system has 12 direct disk blocks, as well as single, double, and triple indirect disk blocks. What is the maximum size of a file that can be stored in this file system?You must show your calculation to receivecredit.

  1. [30 points] ProgrammingProblems

Strictly speaking, this is not really a programming problem, but more like an interactive experimentation.

11.13[modified preparation instruction] Before starting this problem, create two text files namedfile1.txt, file3.txt(butnotfile2.txt!!) in a Unix or Linux-like system (i.e., uses inodes in its file system) with unique contents. Next, obtain the inode number of this file with the command

ls -li file1.txt

This will produce output similar to the following:

16980-rw-r–r– 2 os os 22 Sep 14 16:13 file1.txt

where the inode number is boldfaced. (The inode number offile1.txtis likely to be different on your system.)

The UNIXlncommand creates a link between a source and target file. This command works as follows:

ln [-s] <source file> <target file>

UNIX provides two types of links: (1) hard links and (2) soft links. A hard link creates a separate target file that has the same inode as the source file. Enter the following command to create a hard link betweenfile1.txtandfile2.txt:

ln file1.txt file2.txt

    1. [5points]

What are the inode values offile1.txtandfile2.txt?Are they the same or different? Do the two files have the same—or different— contents?

    1. [5points]

Next, editfile2.txtand change its contents. After you have done so, examine the contents offile1.txt.Are the contents offile1.txtandfile2.txtthe same or different?

    1. [5points]

Next, enter the following command which removesfile1.txt:rm file1.txt

Doesfile2.txtstill exist as well?

    1. [5points]

Now examine the man pages for both thermandunlinkcommands. Afterwards, remove

file2.txtby entering the command

strace rm file2.txt

Thestracecommand traces the execution of system calls as the commandrmfile2.txt

is run. What system call is used for removingfile2.txt?

    1. [10points]

A soft link (or symbolic link) creates a new file that “points” to the name of the file it is linking to. In the source code available with this text, create a soft link tofile3.txtby entering the following command:

ln -s file3.txt file4.txt

After you have done so, obtain the inode numbers offile3.txtandfile4.txtusing the command

ls -li file*.txt

Are the inodes the same, or is each unique? Next, edit the contents offile4.txt. Have the contents offile3.txtbeen altered as well? Last, deletefile3.txt. After you have done so, explain what happens when you attempt to editfile4.txt.

  1. Programming Exercise – to be posted separately with its own duedate

Assignment 10 – Part Two


The purpose of this assignment is to give you a chance to think about the algorithms and data structures needed for a file system at a high level. There are a lot of details that need to be worked out, including the secondary storage structure, caching, concurrency, and of course metadata. The reason for using Python is that it can be thought of as “executable pseudocode” and lets you think about the concepts at a relatively high level by taking care most of the low-level mechanisms.

  1. [20 points] DataStructures

(Download thetemplateand rename A file system is a structure on top of data storage. A storage device contains its own structure (week 12, slide 10). The optional boot-control block and partition-control block can be considered as lower-level structures for the disk rather than for the file system, and we will leave them out for the purpose of this assignment. Instead, we will work on

    1. list of directory control blocks(DEntry)

    2. list of file control blocks(FCB)

    3. datablocks

The two data structures to define are named DEntry and FCB. Before defining them, we observe that they have several things in common, so we define a base class.


definit(self, createTime=None, accessTime=None, modTime=None):


ifcreateTimeisNone: createTime = time.asctime()

ifaccessTimeisNone: accessTime = createDate


modTime = createTime self.createTime = createTime self.accessTime = accessTime self.modTime = modTime

    1. FCB: file controlblock

FCB is a data structure that defines a file on storage structure. That is, it holds metadata including the last access time and the reference to the actual storage. The reference itself depends on the allocation method (slide 23): contiguous allocation, linked allocation, and indexed allocation. For simplicity, we can just use indexed allocation (i.e., a list in Python to maintain the logical-to-physical mapping of block numbers).

In addition, the FCB resides on disk but the OS also keeps a copy in its system-wide

open-file table when the file is open. Because a given file can be opened multiple times by different processes, the OS keeps an open count — in the in-memory copy of FCB –that is incremented on each open() and decremented on each close(). When the count reaches zero, the FCB entry is removed from the system-wide open-file table.



ControlBlock.init(self) #inherit superclass definition self.index=[] #logicaltophysical block mapping self.linkCount= 0 # num ofdirectores with hard linkto itself.openCount= 0 #thisis forin-memory structure,not fordisk

defnBlocks(self): #numberofdisk blocks takenby thefile






Metadata such as the last access date, last modified date, file read/write permission, are also stored in the FCBs (see slide 10), and in this case in its superclassControlBlock. Since the name is kept in the directory, rather than in the FCB, (and the same file may appear in multiple directories due to linking), you can find the name of the file only in the context of a directory. So, here is a method for getting the file name for an FCB:

defnameInDir(self, d):

ifself in d.content:[d.content.index(self)]


    1. DEntry [20points]

A DEntry, also called a directory control block, is a data structure that keeps track of the content of the directory, which can be files (FCB) and nested directories (DEntry).

We include some utility methods: name() is a way to get the directory’s own name. Since the DEntry does not record the directory’s own name, it needs to look into its parent (if any) and find its own name.


definit(self, parent=None):

ControlBlock.init(self) #inherit superclassdefinitionself.parent=parent #linkto theparent directory self.content= [ ] #couldbe FCB orDEntry

self.names=[] # thecorresponding namesoffileordir

defname(self):# get thedirectory namein itsparent,ifany.




deflookup(self, name):

#findthe FCU orDEntry using name,orNoneif notfound

fori, ninenumerate(self.names):

ifn == name:



Your are to write four methods to the DEntry class. Note that name is a local name in the directory, rather than a path.

[5 points]

defaddFile(self, fcb, name):

# add afileto thedirectory underthegivenname.

# * if thenameisalreadyin thedirectory, raiseanexception.# * add the fcb to thecontent list,

# * add the name to the names list.

# *incrementthelinkCountofthis fcb.# *updatethelast modified dateofself.

[5 points]

defrmFile(self, fcb):

#removeafile fromtheDEntry. this doesnotreclaim space.# *decrementthelinkCountof the FCBcorrespondingtoname.# *removethename fromthelistand the FCBfromthecontent.# (hint:you can use the deloperatorinPythontodelete

# anelementof alist)

# * updates the last modified date of this directory

[5 points]

defaddDir(self, dEntry, name):

# it issimilartoaddFile exceptit is adirectory,not afile.# thedifferenceis adirectoryhas aparent.

# * if thenameisalreadyin thedirectory, raiseanexception.# * add thedEntryto thedirectory content.

[5 points]

# * add the name to the names list.

# * set theparentofdEntrytothis directory(self).# *update this directory last modification date.

# it also needs to update the last modified date of self.

defrmDir(self, d):

#removeadirectorydfrom self.itdoesnotreclaimspace.# *findthepositionof d inthis directory content,

# *delete bothdfrom contentandname from nameslist.# *updatesthelast modified dateofself.

# * set the removed dEntry’s parent to None.

Test yourcntlblks.pyusing the test cases provided. To help visualize better, we encode the directory tree and files using a tuple representation. Directory names end with ‘/’ and are the initial member of the tuple, while others are files. This is a sample output:


input directory tree=(‘/’, (‘home/’, (‘u1/’, ‘hello.c’), (‘u2/’, ‘world.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

tuple reconstructed from directory=(‘/’, (‘home/’, (‘u1/’,‘hello.c’),(‘u2/’, ‘world.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

creation timefor/home/u1/hello.cisFriDec 105:49:442017

  1. [30 points] PFS: a simple file system, partone

(Download thetemplateand rename We build up a simple file system structure using the data structure from the previous section. We define it as a Python class with some essential parameters including the number of disk blocks and the directory control blocks (i.e., DEntry) starting from the root directory. From there, the file system needs to keep track of

    1. all file control blocks (FCB) in the file system — in a list datastructure

    2. all DEntry’s in the file system — in a list datastructure

    3. allfreeblocks–inaset(集合)datastructure

    4. system-wide open-file table — in alist

    5. the open count of each entry in the system-wide open-file table — in alist,which just tests data structures, we now have the file system class (PFS) manage the pre-allocated FCBs and DEntrys, and they ultimately map to the storage blocks. Conceptually, all these on-disk structures also get stored in the disk blocks, but for simplicity, we don’t mixthem.

In part-one of the PFS, we work on the structure of the file system first. The block allocation and deallocation algorithm will be done in part-two of PFS (next assignment) and we put placeholder routines fornow.



definit(self, nBlocks=16, nDirs=32, nFCBs=64): self.nBlocks = nBlocks

self.FCBs = [ ] # file control blocks

self.freeBlocks=set(range(nBlocks))#initiallyallblocksfree self.freeDEntrys=[DEntry()foriinrange(nDirs)] self.freeFCBs=[FCB()foriinrange(nFCBs)] self.sysOpenFileTable=[]

self.sysOpenFileCount=[][Noneforiinrange(nBlocks)] #physicalstorage


f =self.freeFCBs.pop()#grab fromthepool FCB.init(f) #reinitializeitlikea newFCBreturnf

deffreeFCB(self, f): self.freeFCBs.append(f)


# write your own for DEntry, analogous to allocFCB

deffreeDEntry(self, d):

# write your own for DEntry, analogous to freeFCB

You are to add the following methods to the PFS class for now: [5 points]

defcreateFile(self, name, enclosingDir):

#allocatea new FCB andupdateitsdirectorystructure:# * ifdefault directoryisNone,set it toroot.

# * parse the path into enclosing directory and filename.

# *allocatea newFCB,add it to theenclosingdir byname,# *appendto the FCBlistof thefilesytem.

# Note: this does not allocate blocks for the file.

[5 points]

defcreateDir(self, name, enclosingDir):

#createa newdirectory under nameinenclosingdirectory.# *checkifname already exists;if so,raise exception.# *allocateaDEntry,add it toenclosingdirectory,

# * return the new DEntry.

[5 points]

defdeleteFile(self, name, enclosingDir):

# *lookupthe fcb bynamein theenclosingdirectory.

# * iflinkCountis 1(which means aboutto be 0afterdelete)# and thefileisstill openedbyothers,then

# raiseanexception about unabletodelete openfiles.

# *call rmFileonenclosingDirtoremovethe fcb(andname).# * if nomore linkCount, then

# *recycle freetheblocks.# *recyclethefcb

[5 points]

defdeleteDirectory(self, name, enclosingDir):

# *lookupthedentrybynamein theenclosingdirectory.# * if thedirectoryis notempty, raise exception about# unabletodelete nonemptydirectory.

# *call rmDironenclosingdirectory# *recyclethedentry

[5 points]

defrename(self, name, newName, enclosingDir):

# *checkifnewNameisalreadyinenclosingDir, raiseexception# *find positionofnameinnames listofenclosingDir

# * change the name to newName in that list

# * set last modification time of enclosing directory

[5 points]

defmove(self, name fromDir, toDir):

# *checkifnameisalreadyintoDir, raiseexception# *lookup nameand see if it isdirectoryorfile.

# * ifdirectory, removeitfrom fromDir(bycallingrmDir),# add it totoDir(bycallingaddDir)

# * iffile, removeitfrom fromDir(bycallingrmFile)# add it totoDir(bycallingaddFile)

Test yourpfs.pyusing the test cases provided in the template. We build up the directories and files like before, except we call the file system routines (e.g.,allocFCB(), freeFCB(), allocDEntry(), freeDEntry()instead of calling the constructor directly). We also get to call higher level functions, including rename, move, etc.

Here is a sample output of the test case: (your output won’t look exactly like this due to time differences)


input directory tree=(‘/’, (‘home/’, (‘u1/’, ‘hello.c’, ‘myfriend.h’),

(‘u2/’, ‘world.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

directory=(‘/’, (‘home/’, (‘u1/’, ‘hello.c’, ‘myfriend.h’), (‘u2/’,

‘world.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

last modification datefor/home/u1/isFriDec 120:29:572017

after renaming=(‘/’, (‘home/’, (‘u1/’, ‘’, ‘myfriend.h’), (‘u2/’,

‘world.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

last modification datefor/home/u1/isFriDec 120:30:02 2017 after moving=(‘/’, (‘home/’, (‘u1/’, ‘’), (‘u2/’,‘world.h’,

‘myfriend.h’), ‘homefiles’), (‘bin/’, ‘ls’), (‘etc/’,))

after moving=(‘/’, (‘home/’, (‘u1/’, ‘’, (‘etc/’,)), (‘u2/’,

‘world.h’, ‘myfriend.h’), ‘homefiles’), (‘bin/’, ‘ls’))

Note: The PFS class will be continued in the next assignment.