Student: Yu Cheng (Jade)
ICS 412
Homework #5
November 16. 2009
Homework #5
Exercise 8.11: Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how
would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB,
112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?
a. First-fit
Answer: 212 KB 500 KB 100 KB, 288 KB, 200 KB, 300 KB, 600 KB
417 KB 600 KB 100 KB, 288 KB, 200 KB, 300 KB, 183 KB
112 KB 288 KB 100 KB, 176 KB, 200 KB, 300 KB, 183 KB
426 KB Wait (no partition is large enough) 100 KB, 176 KB, 200 KB, 300 KB, 183 KB
b. Best-fit
Answer: 212 KB 300 KB 100 KB, 500 KB, 200 KB, 88 KB, 600 KB
417 KB 500 KB 100 KB, 83 KB, 200 KB, 88 KB, 600 KB
112 KB 200 KB 100 KB, 83 KB, 88 KB, 88 KB, 600 KB
426 KB 600 KB 100 KB, 83 KB, 88 KB, 88 KB, 174 KB
c. Worst-fit
Answer: 212 KB 600 KB 100 KB, 500 KB, 200 KB, 300 KB, 388 KB
417 KB 500 KB 100 KB, 83 KB, 200 KB, 300 KB, 388 KB
112 KB 388 KB 100 KB, 83 KB, 200 KB, 300 KB, 276 KB
426 KB Wait (no partition is large enough) 100 KB, 83 KB, 200 KB, 300 KB, 276 KB
d. Which algorithm makes the most efficient use of memory?
Answer: Best-fit algorithm makes the most efficient use of memory. It is the only method capable of
meeting all memory requests in this case.
Exercise 2: Consider the following page table, in which “x” means an invalid entry.
Logical Physical
15 x
14 x
13 x
12 x
11 7
10 x
9 5
8 x
7 x
6 x
5 3
4 4
3 0
2 6
1 1
0 2
Assume a 4 KB page size. Give the physical address corresponding to the following logical
addresses. All addresses are decimal values.
a. 20
Answer: To calculate the physical address of the given logical address, when the page size is 4 KB, we have,
20 4
0
0
2
2 4 / 8
8 20 8020 .
The physical address of logical address 20 B is at physical address 8020 B.
b. 4100
Answer: To calculate the physical address of the given logical address, when the page size is 4 KB, we have,
4100 / 1000 4.1 2 4
1
1
1
1 4 / 4
4 4.1 4 4100 .
The physical address of logical address 4100 B is at physical address 4100 B.
c. 8300
Answer: To calculate the physical address of the given logical address, when the page size is 4 KB, we have,
8300 / 1000 8.3 3 4
2
2
6
6 4 / 24
24 8.3 8 24300 .
The physical address of logical address 8300 B is at physical address 24300 B.
Exercise 8.18: Consider a logical address space of 32 pages with 1024 words per page, mapped onto a physical
memory of 16 frames.
a. How many bits are required in the logical address?
Answer: The logical address requires 5 bits for the page number because there are 32 2" of them. Then,
the logical address requires 10 bits of the offset because there are 1024 2#$ of them. So, the
logical address requires a total is 15 bits.
b. How many bits are required in the physical address?
Answer: The physical address requires 4 bits for the frame number because there are 16 2% of them.
Then, the physical address also requires 10 bits of the offset because there are 1024 2#$ of
them. So, the physical address requires a total is 14 bits.
Exercise 8.19: Consider a computer system with a 32-bit logical address of 4-KB page size. The system supports
up to 512 MB of physical memory. How many entries are there in each of the following?
a. A conventional single-level page table.
Answer: 2## 4000 2#& , so we need 12 out of 32 bit logical address for the offset. Then we have
32 12 20 bits left for the page number. There are, therefore, 2&$ 1048576 entries in a
conventional single-level page table.
b. An inverted page table.
Answer: 2## 4000 2#& , so we still need 12 out of 32 bit logical address for the offset. Then we have
32 12 20 bits left for the page number and process id. There are, therefore, 2&$/& 2#$
1024 entries in a conventional single-level page table.
Exercise 5: Suppose we have a computer system with a 44-bit virtual address, page size of 64 KB, and 4 bytes
per page table entry.
a. How many pages are in the virtual address space?
Answer: 2#" 64000 2#) , so we need 16 out of 44 bit logical address for the offset. Then we have
44 16 28 bits left for the page number. There are, therefore, 2&* 268435456 pages in
the virtual address space.
b. Suppose we use two-level paging and arrange for all page tables to fit into a single page frame.
How will the bits of the address be divided up?
Answer: 2#" 64000 2#) , so we still need 16 out of 44 bit logical address for the offset. Since we have
4 bytes per page table entry, one page frame can fit 64 /4 16000 page entries. We need
14 bits, as 2#+ 16000 2#% , to index into a page of the page table. Then we have 44 16
14 14 bits left for the page number.
43 42 ... 30 29 28 ... 16 15 14 ... 0
|--outer--| |--inner--| |-offset-|
Exercise 8.23: Consider the following segment table:
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?
a. 0,430
Answer: 219 430 649 . Segment 0 has a length of 600, which is greater than 430.
b. 1,10
Answer: 2300 10 2400 . Segment 1 has a length of 14, which is greater than 10.
c. 2,500
Answer: Illegal reference. Segment 2 doesn’t have a corresponding base.
d. 3,400
Answer: 1327 400 1727 . Segment 3 has a length of 580, which is greater than 400.
e. 4,112
Answer: Illegal reference. Segment 4 has a length of 96, which is less than 112.
