Assignment #11 Solution

$30.00

Description

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

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

  • Section 2: Python source files. Include your name and student ID in the program comments ontop.

    • Section 2.1:cntlblks.py,pfs.py,typescript1

    • Section 2.2:proc.py,typescript2

  • Section 3: Python source files. Include your name and student ID in the program comments ontop.

    • disk.py,typescript3

  1. [30 points] ProblemSet

You must elaborate to receive full credit.

    1. [10 points]12.2Explain why SSDs often use an FCFS disk schedulingalgorithm.

    1. [20 points]12.10Compare the throughput achieved by a RAID level 5 organization with that achieved by a RAID level 1 organization for thefollowing:

      1. Read operations on singleblocks

      2. Read operations on multiple contiguousblocks

  1. Programming Exercise: File Systemscontinued

—— updated 12/6 18:00 ——

(You can use the providedtemplatecombine withcntlblks.pycandpfsHW10.pyc, and rename them aspfs.py,cntlblks.pyc,pfsHW10.pycrespectively. Or you can also use your owncntlblks.pyandpfs.pyfrom HW10 Part 2)

—————————————

This is a continuation of the programming assignment fromAssignment 10 Part 2. It consists of block allocation algorithms and free space management, as well as process-level API.

    1. [5 points] Data Structures for block allocation and free space management

      • index for allocation (per file, associated with theFCB)

      • set (bitmap) for free block management (per filesystem)

Note that an FCB would technically link to the index rather than contain it, and the index would take up space on disk. For convenience, we define the index as a field in the FCB class. Note the alternatives to index, including linked blocks, multi-level index, and inode.

An index is an array that maps logical block numbers of the file to the physical block numbers. In a way, it is like a page table except for disks blocks, and you only have to have as many blocks as the file contains, rather than the entire address space.

A bitmap can be an efficient implementation for a set. A set is a collection of (unordered) members. Operations include membership test, intersection, difference, union, etc Fortunately, Python supports sets as a native data structure. A set can be converted to/from lists and tuples.

Observe from the part of PFS code from last assignment:

classPFS:

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

self.FCBs = [ ]

self.freeBlockSet= set(range(nBlocks))

.. #note:wasfreeBlocksbutshouldbechangedtonameinredself.storage=[Noneforiinrange(nBlock)]

defreadBlock(self, physicalBlockNumber):

returnself.storage[physicalBlockNumber]

defwriteBlock(self, physicalBlockNumber, data): self.storage[physicalBlockNumber]=data

Write two methods for the PFS class and run the test case:

defallocateBlocks(self, nBlocksToAllocate):

#allocates free blocks fromthepoolandreturnthe setof#block numbers

# * if there are not enough blocks, then return None

# *findS =nBlocksToAllocate members fromthefreeset# *removeSfromthefreeset

# * return S

deffreeBlocks(self, blocksToFree):

#blocksToFreeis the set ofblock numbersasreturnedfrom#allocateBlocks().

# * set thefreeset tounion withtheblocksToFree.

# * strictly speaking, those blocks should also be erased.

Test your block allocation code before proceeding to the next section. You may use the following test case:

deftestBlockAlloc(fs): print(‘freeblocks=%s’%fs.freeBlockSet)a =fs.allocateBlocks(5)

b =fs.allocateBlocks(3)c =fs.allocateBlocks(2)d =fs.allocateBlocks(1)e =fs.allocateBlocks(4)

print(‘allocate (5)a=%s, (3)b=%s, (2)c=%s, (1)d=%s, (4)e=%s’%(a,b,c,d,e))

print(‘freeBlockSet=%s’%fs.freeBlockSet)fs.freeBlocks(b)

print(‘after freeBlocks(%s), freeBlockSet=%s’% (b,fs.freeBlockSet))fs.freeBlocks(d)

print(‘after freeBlocks(%s), freeBlockSet=%s’% (d,fs.freeBlockSet))f =fs.allocateBlocks(4)

print(‘after allocateBlocks(4)=%s, freeBlockSet=%s’%(f,fs.freeBlockSet))

fs.freeBlocks(a | c)

print(‘after freeBlocks(a|c)=%s, freeBlockSet=%s’%(a|c,fs.freeBlockSet))

Instantiate your file system with a minimum block count of 16. Then you can expect the following output: (your order may vary)

freeblocks={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

allocate (5)a={0,1, 2, 3, 4},(3)b={5,6, 7},(2)c={8,9},(1)d={10},

(4)e={11, 12, 13, 14}

freeBlockSet={15}

after freeBlocks({5, 6, 7}), freeBlockSet={5, 6, 7, 15}

after freeBlocks({10}), freeBlockSet={5, 6, 7, 10, 15}

after allocateBlocks(4)={10, 5, 6, 7}, freeBlockSet={15}

after freeBlocks(a|c)={0, 1, 2, 3, 4, 8, 9}, freeBlockSet={0, 1, 2, 3, 4, 8,

9, 15}

    1. [40 points] Process-Level FileAPI

Next, you are to write four methods for the process-level file API. Note that the file system maintains system-wide state as well as per-process state. The process state includes

      • list of “per-process file entry”, each ofwhich

        • references the FCB in the system-wide processtable

        • contains the “file head position” of each open file by the process — this is wherethenextread()orwrite()willtakeplacewithinthefile.Forsimplicity, we just keep track of the logical block number, rather than the actual byte position.

      • current working directory and homedirectory

We declare the following data structures (downloadtemplateand rename asproc.py)

frompfsimport*

classPerProcessFileEntry: ”’

thisis thedata structurefor theper-process open-filetable.Itcontainsareferenceto thesystem-wide open-file table, plus additional state, includingtheposition.

”’

definit(self, fcb): self.fcb = fcb

self.pos=0 # thelogical position (block)of the”filehead”

classProcessFS:

definit(self, fs, homePath):

self.openFileTable =[] #listofreferencestosystem-wideOFTself.homePath=homePath

self.fs = fs

self.cwd, filename = self.fs.parsePath(homePath, None)

You are to write four methods for the ProcessFS class:open(), close(), read(),andwrite().

defopen(self, filepath): ”’

”’

open filebyname, readits FCBinto in-memory open-filetable.add to thesystem-wide open file table. return filedescriptor,whichisindex into per-process open filetable.

set file-head to zero

# thecaller provides path including directorytofile.#parseto getdirectory referenceandfile name.

enclosingDir, filename = self.fs.parsePath(filepath, self.cwd)

#findthe FCBunderthegiven file namein theenclsoingdir# if notfoundor notfile, raiseexception.

# if the FCB is notalreadyin thesystem-wide open filetable,#thenadd it, andincrementitsopencount.

#createaper-process file entryforthisFCB,# put it in theper-process open filetable,

#andsetthedescriptor(anint)tobeitsindexinthetable.#updatethelast-accesstime

# return the descriptor.

defclose(self, descriptor): ”’

removestheentryin theper-process open-file table, decrementthecountinsystem-wide open-file tableentry,

if count zero

remove entry in system-wide table

update metadata to disk-based directory structure

”’

#findtheper-process file entry usingdescriptor#extracttheFCB, decrementitsopen count

# if nomore open count, deleteitsentryin thesystem-wide# open-filetable.

# clear its per-process open file entry.

defread(self, descriptor,nBlocks=1):”’

readthefile starting from current blockfornBlocksincrementthefile-headbynBlocks

return the data read

”’

#findtheper-process file entry usingdescriptor# get thefile-head positionand FCB

# (assume file-head points at the block to read)

#readoneblockat atimeup toeither nBlocksor end offile# basedon thelogical-to-physicalmapping

#incrementthefile head, appendthedatato thereturn valuevar#updatethelast access time

# return the data

defwrite(self, descriptor,data):”’

writethefile sequentiallyfornblocks from file headpos.,byextending fileifnecessary.

forsimulation, datais alistofstrings, where each stringis thecontentfor oneblock.solen(data)is thenumberofblocks

”’

# find the per-process file entry

#extracttheposition, FCB,andlogical-to-physicalindex#checkif weneedtoallocate more blocks

#ifenough,addthenewlyallocatedonestotheendofthefile# (hint:byextendingtheindex)

# but if not enough, raise an exception

#writeoneblockat atime from current headposition#increment file head positionforeach block written#updatethelast-modification time.

You need to test your code. You may use test cases provided and get the following output (but your time may differ)

$python3 proc.py

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.cisMonDec 421:28:362017f2read=hello

f2read=world

  1. Disk Scheduling Algorithms [25points]

In Part 3, you are to implement the disk (seek) scheduling algorithms covered in Chapter 12. Use the following template (downloadand rename asdisk.py):

classDiskScheduler:

_POLICIES = [‘FCFS’, ‘SSTF’, ‘SCAN’, ‘LOOK’, ‘C-SCAN’, ‘C-LOOK’]

definit(self, nCylinders): self.nCylinders = nCylinders

defschedule(self, initPos, requestQueue, policy, direction):”’

requestis thelistofcylinderstoaccesspolicyis one of thestringsin_POLICIES.

directionis’up’or’down’andappliesto(C-)SCAN/LOOKonly.returnsthelistfor theorderofcylinderstoaccess.

”’

ifpolicy == ‘FCFS’:

# return the disk schedule for FCFS

ifpolicy == ‘SSTF’:

# compute and return the schedule for shortest seek time first

ifpolicyin[‘SCAN’, ‘C-SCAN’, ‘LOOK’, ‘C-LOOK’]:

#sequentiallyonedirectionto one end (up ordown),#then sequentiallyinopposite direction.

# compute and return the schedule accordingly.

deftotalSeeks(initPos,queue):lastPos=initPos totalMoves=0

forp inqueue:

totalMoves+=abs(p-lastPos)lastPos=p

returntotalMoves

ifname ==’main‘:

defTestPolicy(scheduler, initHeadPos, requestQ, policy, direction):s =scheduler.schedule(initHeadPos, requestQ, policy, direction)t =totalSeeks(initHeadPos,s)

print(‘policy %s %s (%d): %s’ % (policy, direction, t, s))

scheduler = DiskScheduler(200)

requestQueue = [98, 183, 37, 122, 14, 124, 65, 67]

initHeadPos = 53

forpolicyinDiskScheduler._POLICIES:

ifpolicy[:2]==’C-‘orpolicy[-4:]in[‘SCAN’, ‘LOOK’]: TestPolicy(scheduler, initHeadPos, requestQueue, policy, ‘up’) TestPolicy(scheduler, initHeadPos, requestQueue, policy,’down’)

else:

TestPolicy(scheduler, initHeadPos, requestQueue, policy, ”)

print(‘more tests on SCAN and C-SCAN’)

rQs =[[98,37, 0,122, 14], [98,37,199, 122, 14], [98,0, 37,199,

14]]

forqinrQs:

print(‘Q=%s’ % q)

forpolicyin[‘SCAN’, ‘C-SCAN’]:

fordirectionin[‘up’, ‘down’]:

TestPolicy(scheduler, initHeadPos, q, policy, direction)

You can expect to get output like this:

$python3 disk.py

policy FCFS (640): [98, 183,37,122,14,124,65,67]

policy SSTF (236): [65,67, 37, 14, 98,122, 124,183]

policy SCANup(331): [65,67, 98,122, 124, 183, 199,37,14]

policy SCAN down (236): [37,14, 0, 65, 67, 98,122, 124,183]

policy LOOK up (299): [65, 67, 98, 122, 124, 183, 37, 14]

policy LOOK down (208): [37, 14, 65, 67, 98, 122, 124, 183]

policy C-SCANup(382): [65,67, 98,122, 124, 183, 199,0, 14,37]

policy C-SCAN down (386): [37,14, 0,199, 183, 124, 122,98, 67,65]

policy C-LOOK up (322): [65, 67, 98, 122, 124, 183, 14, 37]

policy C-LOOK down (326): [37, 14, 183, 124, 122, 98, 67, 65]

more tests on SCAN and C-SCAN Q=[98, 37, 0, 122, 14]

policy SCAN up (345): [98, 122, 199, 37, 14, 0]

policy SCAN down (175): [37, 14, 0, 98, 122]

policy C-SCAN up (382): [98, 122, 199, 0, 14, 37]

policy C-SCAN down (353): [37, 14, 0, 199, 122, 98]

Q=[98, 37, 199, 122, 14]

policy SCAN up (331): [98, 122, 199, 37, 14]

policy SCAN down (252): [37,14, 0, 98,122,199]

policy C-SCANup(382): [98, 122, 199,0, 14,37]

policy C-SCAN down (353): [37, 14, 0, 199, 122, 98]

Q=[98, 0, 37, 199, 14]

policy SCAN up (345): [98, 199, 37, 14, 0]

policy SCAN down (252): [37,14, 0, 98,199]

policy C-SCANup(382): [98, 199,0, 14,37]

policy C-SCAN down (353): [37, 14, 0, 199, 98]