Assignment #8 Solution

$30.00

Description

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

  • one PDF file namedhw8.pdffor Section 1 and Section 2.3 (bonus).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, 2.2:memalloc.py,typescript1

    • Section 2.3 (bonus): show your code and output in your malloc.py and typescript 1, plus written explanation in thePDF.

  1. [40 points] ProblemSet

    1. [10 points] 8.15 Consider a logical address space of 256 pages, with a 4KB page size, mapped onto a physical memory of 64frames.

      1. How many bits are required in the logicaladdress?

      2. How many bits are required in the physicaladdress?

    2. [20 points] 8.16 Consider a computer system with a 32-bit logical address and 4-KB page size. The system supports up to 512-MB of physical memory. How many entries are there in each of thefollowing?

      1. A conventional single-level pagetable

      2. An inverted pagetable

    3. [10 points] 8.20 Consider the following segmenttable:

Segment

Base

Length

0

219

600

1

2300

14

2

90

100

3

1327

580

4

1952

96

What are the physical addresses for the following logical addresses?

      1. 0, 430 (segment#, logicaladdress)

b. 1, 10

c. 2, 500

d. 3, 4000

e. 4, 112

  1. [60 points] ProgrammingExercise

In this programming exercise, you are to implement algorithms for contiguous memory allocation, similar tomalloc()andfree()in the standard library(stdlib).

malloc(), for memory-allocate, is a stdlib function for dynamically allocating a contiguous block of memory. The parameter is the number of bytes to allocate. The return value is the pointer (here anintin Python) to the allocated memory block, orNoneif it cannot be allocated, possibly due to memory fragmentation.

free()will free a previously allocated memory (as returned by a previous call tomalloc()).The textbook talks about three policies: First-Fit, Best-Fit, and Worst-Fit. You are to implement all three policies in Python. Use the following API:

classMemAlloc:

_POLICIES = (‘FirstFit’, ‘BestFit’, ‘WorstFit’)

definit(self, totalMemSize, policy = ‘BestFit’):

if notpolicyinMemAlloc._POLICIES:

raiseValueError(‘policy mustbe in %s’ %MemAlloc._POLICIES) self.allocation= { } # usethis dictionaryto mapallocated

#pointerto theallocatedsize

#keepalistofholes, whicharetuples with (pointer,size)self.holes=[(0, totalMemSize)]#sortingbypointer

# your own code here …

defmalloc(self, reqSize):

”’returnthestarting addressof theblockofmemory,orNone”’#your code here

deffree(self, pointer):

”’freethepreviously allocated memory startingatpointer”’#your code here

You will find some test cases in thetemplatefile. Rename itmemalloc.py

    1. [30 points]malloc()

malloc() and free() use of two data structures:

      • list of holes(self.holes),which consists of tuples (address,size)

      • mapping from allocated addresses to sizes(self.allocation)malloc()williterateoverthelistofholes,keptinsortedorderbyaddress.

      • if the policy is First-Fit, then it uses the first hole that is big enough to serve the requestedsize

      • if the policy is Best-Fit, then it continues looking for the smallest hole that is big enough to serve the requestedsize.

      • if the policy is Worst-Fit, then it looks for the biggest hole that can serve the requestedsize.

If no holes are big enough, thenmalloc()returnsNone.But if there is one hole that can work, then

      • if the chosen hole is used up completely by this malloc request, then it should be deleted from the list ofholes.

      • Otherwise, if there is still some remaining unused space in this hole, then update the hole’s address andsize.

In any case, the new allocation should be recorded in theself.allocationdictionary. Use the address as the key and size as the value. Finally, return the address for the newly allocated memory chunk.

You should test this part thoroughly, possibly with your own test cases, before proceeding to the next part.

    1. [30 points] free(void*p)

free()is the inverse operation ofmalloc().It takes a previously allocated address as parameter, looks up the size from the allocation, and

      • update the holeslist

      • delete the freed entry from the allocationdictionary

Updating the holes list is potentially the tricky part, because there are several possible cases. Let (p, s) denote the pointer to the freed block and the size of the block to be freed.

      • if empty holes list: just add (p, s) to the holeslist.

      • if (p, s) goes before the first hole on thelist:

        • if (p, s) and first hole are disjoint, just prepend (p, s) to holeslist

        • if contiguous, then merge (p, s) into the first hole by updating the first hole’s starting address andsize.

      • if (p, s) goes after the last hole on thelist:

        • mirror image to the “before the firsthole”

      • if (p, s) goes between hole [i] and hole[i+1]:

        • if all three are contiguous, merge all three (and delete hole[i+1])

        • if (p, s) contiguous with [i], mergethem

        • if (p, s) contiguous with [i+1], mergethem

        • if all three are disjoint, insert (p, s) between [i] and [i+1] on the list Here is sampleoutput:

a=malloc(10):

FirstFit symbols={‘a’: 0} holes=[(10, 10)] allocation={0: 10}

BestFit symbols={‘a’: 0} holes=[(10, 10)] allocation={0: 10}

WorstFit symbols={‘a’:0}holes=[(10, 10)] allocation={0:10}b=malloc(1):

FirstFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}

BestFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}

WorstFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}c=malloc(4):

FirstFit symbols={‘a’: 0, ‘b’: 10, ‘c’: 11} holes=[(15, 5)] allocation={0:

10, 10: 1, 11: 4}

BestFit symbols={‘a’: 0, ‘b’: 10, ‘c’: 11} holes=[(15, 5)] allocation={0:

10, 10: 1, 11: 4}

WorstFit symbols={‘a’: 0, ‘b’: 10, ‘c’: 11} holes=[(15, 5)] allocation={0:

10, 10: 1, 11: 4}

free(c)

FirstFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}

BestFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}

WorstFit symbols={‘a’:0,‘b’:10}holes=[(11,9)]allocation={0:10, 10:1}free(a)

FirstFit symbols={‘b’: 10} holes=[(0, 10), (11, 9)] allocation={10: 1}

BestFit symbols={‘b’: 10} holes=[(0, 10), (11, 9)] allocation={10: 1}

WorstFit symbols={‘b’:10}holes=[(0, 10), (11,9)]allocation={10:1}d=malloc(9):

FirstFit symbols={‘b’: 10, ‘d’: 0} holes=[(9, 1), (11, 9)] allocation={10:

1, 0: 9}

BestFit symbols={‘b’:10,‘d’:11}holes=[(0, 10)] allocation={10:1, 11: 9}

WorstFit symbols={‘b’: 10, ‘d’: 0} holes=[(9, 1), (11, 9)] allocation={10:

1, 0: 9}

e=malloc(10):

FirstFit symbols={‘b’: 10, ‘d’: 0, ‘e’: None} holes=[(9, 1), (11, 9)]

allocation={10: 1, 0: 9}

BestFit symbols={‘b’: 10, ‘d’: 11, ‘e’: 0} holes=[] allocation={10: 1, 11:

9, 0: 10}

WorstFit symbols={‘b’: 10, ‘d’: 0, ‘e’: None} holes=[(9, 1), (11, 9)]

allocation={10:1, 0:9}

————————

a=malloc(3):

FirstFit symbols={‘a’: 0} holes=[(3, 17)] allocation={0: 3}

BestFit symbols={‘a’: 0} holes=[(3, 17)] allocation={0: 3}

WorstFit symbols={‘a’:0}holes=[(3, 17)] allocation={0:3}b=malloc(6):

FirstFit symbols={‘a’: 0, ‘b’: 3} holes=[(9, 11)] allocation={0: 3, 3: 6}

BestFit symbols={‘a’: 0, ‘b’: 3} holes=[(9, 11)] allocation={0: 3, 3: 6}

WorstFit symbols={‘a’:0,‘b’:3}holes=[(9, 11)] allocation={0:3, 3:6}c=malloc(2):

FirstFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9} holes=[(11, 9)] allocation={0: 3,

3: 6, 9: 2}

BestFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9} holes=[(11, 9)] allocation={0: 3,

3: 6, 9: 2}

WorstFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9} holes=[(11, 9)] allocation={0: 3,

3: 6, 9: 2}

d=malloc(5):

FirstFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(16, 4)]

allocation={0: 3, 3: 6, 9: 2, 11: 5}

BestFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(16, 4)]

allocation={0: 3, 3: 6, 9: 2, 11: 5}

WorstFit symbols={‘a’: 0, ‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(16, 4)]

allocation={0:3, 3: 6, 9: 2, 11:5}free(a)

FirstFit symbols={‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(0, 3), (16, 4)]

allocation={3: 6, 9: 2, 11: 5}

BestFit symbols={‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(0, 3), (16, 4)]

allocation={3: 6, 9: 2, 11: 5}

WorstFit symbols={‘b’: 3, ‘c’: 9, ‘d’: 11} holes=[(0, 3), (16, 4)]

allocation={3:6, 9: 2, 11:5}free(c)

FirstFit symbols={‘b’:3,‘d’:11}holes=[(0,3), (9, 2),(16,4)]

allocation={3: 6, 11: 5}

BestFit symbols={‘b’:3,‘d’:11}holes=[(0,3), (9, 2),(16,4)]

allocation={3: 6, 11: 5}

WorstFit symbols={‘b’:3,‘d’:11}holes=[(0,3), (9, 2),(16,4)]

allocation={3: 6, 11: 5} e=malloc(2):

FirstFit symbols={‘b’:3,‘d’:11,‘e’:0}holes=[(2,1), (9, 2),(16,4)]

allocation={3: 6, 11: 5, 0: 2}

BestFit symbols={‘b’: 3, ‘d’: 11, ‘e’: 9} holes=[(0, 3), (16, 4)]

allocation={3: 6, 11: 5, 9: 2}

WorstFit symbols={‘b’:3,‘d’:11,‘e’:16}holes=[(0,3), (9, 2),(18,2)]

allocation={3:6, 11: 5, 16:2}free(b)

FirstFit symbols={‘d’: 11, ‘e’: 0} holes=[(2, 9), (16, 4)] allocation={11:

5, 0: 2}

BestFit symbols={‘d’:11,‘e’:9}holes=[(0,9),(16,4)]allocation={11:5,

9: 2}

WorstFit symbols={‘d’:11,‘e’:16}holes=[(0, 11), (18,2)]allocation={11:

5, 16: 2}

f=malloc(11):

FirstFit symbols={‘d’: 11, ‘e’: 0, ‘f’: None} holes=[(2, 9), (16, 4)]

allocation={11: 5, 0: 2}

BestFit symbols={‘d’: 11, ‘e’: 9, ‘f’: None} holes=[(0, 9), (16, 4)]

allocation={11: 5, 9: 2}

WorstFit symbols={‘d’: 11, ‘e’: 16, ‘f’: 0} holes=[(18, 2)] allocation={11:

5, 16: 2, 0: 11}

    1. [up to 20 points] Bonus: test case showing advantage ofFirst-Fit

In the provided test cases, we included one example that shows Best-Fit succeeding while the other two fail, and another example showing Worst-Fit succeeding. For this bonus problem, you are to generate a test case that shows First-Fit succeeding and Best-Fit and Worst-Fit fail. You must provide the test case in the same format as in the template. You must provide an explanation in the PDF file and a typescript. If multiple students submit identical test cases, then the bonus points will be divided evenly among them.