CS372: Homework 2

Problem 1: (based on reading; not covered in lecture)

Segmented memory schemes (as well as user-level memory allocators like malloc() and, later in class, some disk placement schemes) use various policies for fitting variable sized allocation units into variable-sized spaces. Concoct a scenario in which Best-fit allocation outperforms First-fit, Worst-fit, and Buddy allocation (see the book for details on these algorithms). Repeat for First-fit v. the others, Worst-fit v. the others, and Buddy allocation v. the others.

Problem 2 (based on reading; not covered in lecture)

Describe the data structures required to implement best-fit memory allocation.

Problem 3

This question refers to an architecture using segmentation with paging. In this architecture, the 32-bit virtual address is divided into fields as follows:

4 bit segment number 12 bit page number 16 bit offset

Here are the relevant tables (all values in dexadecimal):

Segment Table Page Table A Page Table B

0 Page Table A 0 CAFE 0 F000

1 Page Table B 1 DEAD 1 D8BF

x (rest invalid) 2 BEEF x (rest invalid)

3 BA11

x (rest invalid)

Find the physical address corresponding to each of the following virtual addresses (answer "bad virtual address" if the virtual address is invalid):

00000000
20022002
10015555

Segment Table		Page Table A		Page Table B
0	Page Table A	0	CAFE	0	F000
1	Page Table B	1	DEAD	1	D8BF
x	(rest invalid)	2	BEEF	x	(rest invalid)
		3	BA11
		x	(rest invalid)