DOC PREVIEW
MIT 6 826 - Problem Set #2

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 Principles of Computer SystemsPROBLEM SET 2Issued: Tuesday, February 12, 2002 Due: Thursday, February 21, 2002 (updated)The following problems explore implementations and use of file system interfaces.There are three problems in this problem set; please turn in each problem on a separate sheet of paper.Also give the amount of time you spend on each problem.Problem 1. Encrypted File SystemIn this problem your task is to implement the CipherFile module. The CipherFile module is a filter forthe File module at page 6 of Handout 7: it implements the interface of File and uses another instance ofFile internally. The mo dule is parametrized by a pair of a coding and a decoding function that are mutuallyinverse functions:MODULE CypherFile[[code : Byte -> Byte,decode : Byte -> Byte]SUCHTHAT \ [cd,dcd] |cd * dcd = id /\dcd * cd = id]Here id denotes the identity functionid = \ x | xA file is represented as a sequence of encoded bytes:TYPE File = SEQ ByteD = PN -> FVAR d := D{}Ignore the possibility of crashes in this problem.a) Write the abstraction function from CipherFile.d to File.d.b) Implement operations Read and WriteAtomic in CypherFile.c) Using the abstraction function in a), show that CypherFile implements File.d) Is it true in your implementation that, conversely, File implements CypherFile?Problem 2. Run-length Encoding File SystemIn this problem, your task is to design a file system that stores the file contents in compressed form. Youshould formulate this file system as an im plementation of the following MicroFile interface, which is asimplification of the interface at page 6 of the Handout 7. The MicroFile interface ignores the problem ofcrashes.MODULE MicroFile EXPORT PN, Byte, Data, X, F =TYPE PN = String % Path NameWITH {read:= Read, append:= Append}I = IntByte = IN 0 .. 255Data = SEQ Byte1X = Nat % byte-in-file indeXF = Data % FileD = PN -> F % DirectoryVAR d := D{} % undefined everywhereFUNC Read(pn: PN, x: Nat, i: Nat) -> Data =RET d(pn).seg(x,i)APROC Append(pn: PN, b: Byte) = <<d(pn) := d(pn) + { b } >>Compression in this file system is achieved by storing every sequence of n adjacent bytes b as a pair hb, ni.The file content is then represented as a sequence of such pairs and has type CompData.MODULE CompressFileTYPE CompData = SEQ PairByte = MicroFile.BytePair = (Byte, PosInt)PosInt = Int SUCHTHAT (\i | i > 0)D = PN -> CompDataVAR d := D{}For example, the sequence of bytes ’Hello’ is represented as a list[(’H’,1), (’e’,1), (’l’,2), (’o’,1)](Here we have written a character sequence in single quotes as an abbreviation for the corresponding byteor a sequence of bytes.)a) Write the abstraction function mapping CompressFile.d to MicroFile.d.b) The compressed content of every file should be as short as possible. Find a simple sufficient conditionon the values of CompData values that guarantees the shortest encoding. Use SUCHTHAT construct towrite this condition as a SPEC invariant associated with the CompData type.c) Write the implementation of the Read and Append operations in the CompressFile module.d) Consider the set of states that c an be generated by the Read and Append operations on an existingfile in your implementation. Are there multiple states in CompressFile that the abstraction functionmaps to the same state in File?e) Use the abstraction function to show that your CompressFile implements the MicroFile module.Problem 3. Cache Replacement PoliciesThe procedure BufferedDisk.MakeCacheSpace in Handout 7 is not defined. Your goal in this problem isto write two different implementions of this procedure using two different cache replacement policies: LRUand LRUCF.a) LRU (Least Recently Used) policy makes space in the cache by first replacing the block that wasaccessed least recently. Write the implementation of BufferedDisk.MakeCacheSpace using LRU policy.b) LRUCF (Least Recently Used, Clean First) policy makes space in the cache by first replacing blocks thatare clean (not modified compared to their original content). Among the clean blocks, it first replacesthose that were least recently used, using LRU policy. If there are no clean blocks, it choses amongthe dirty blocks using LRU policy. Write the implementation of BufferedDisk.MakeCacheSpace usingLRUCF policy.Try to minimize the number of changes you make to the BufferedDisk implementation from Handout 7.For the changes you m ake, argue informally that the same abstraction function can still be used to showthat BufferedDisk implements BDisk module from Handout


View Full Document

MIT 6 826 - Problem Set #2

Documents in this Course
Consensus

Consensus

10 pages

Load more
Download Problem Set #2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set #2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set #2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?